First Failing Build

Every night your team's code is built and tested, and the builds are numbered 1, 2, 3 and so on up to n. At some point a change slipped in that broke the tests: from that build on, every build fails. Checking a build is slow, so you are given a function is_bad(b) that tells you whether build b fails (True) or passes (False).

Write first_bad_build(n, is_bad) that returns the number of the first failing build. Build n always fails, so there is always an answer. Your function may call is_bad at most 40 times.

Examples

first_bad_build(10, lambda b: b >= 4)       # returns 4
first_bad_build(5, lambda b: b >= 1)        # returns 1
first_bad_build(1000, lambda b: b >= 1000)  # returns 1000

In the first example builds 1 to 3 pass and builds 4 to 10 fail.

Constraints

• 1 <= n <= 2,000,000,000
• Once a build fails, every later build fails too
• At most 40 calls to is_bad

Note

Checking the builds one by one could take two billion calls. Every check you make should rule out about half of the builds that are still possible.