Problem 397134 · easy · Level 03 Linear Management & Searching

First Failing Build

binary search · predicates · higher-order functions

Builds are numbered 1..n. At some point a bug was introduced, and every build from that one onward is broken; all earlier builds are fine. You are given n and a function is_broken(v) that returns True if build v is broken.

Return the number of the first broken build, or -1 if no build is broken.

Examples

Input:  n = 5, is_broken = lambda v: v >= 4
Output: 4

Input:  n = 5, is_broken = lambda v: False
Output: -1

Input:  n = 1, is_broken = lambda v: True
Output: 1

Constraints

  • 1 <= n <= 10**9
  • is_broken is monotone: once it returns True it returns True for every larger build.
  • Call is_broken at most 40 times; checking builds one at a time is too slow.

Goals

  • Binary search over a monotone boolean predicate
  • Detect the 'no True value at all' case
Starting Python…