247. First Bad Version
Your team ships a product as a sequence of versions numbered 1 through n. Somewhere along the way a broken change was merged: one version failed quality control, and because each version is built on top of the previous one, every version after it is broken too. So the check results over 1..n look like a run of good versions followed by a run of bad ones, and at least one bad version is guaranteed to exist.
A checker is already provided for you — is_bad(version) in Python, isBadVersion(version) in C++/Java — which returns whether a given version is bad. Your function receives the integer n and must return the number of the first bad version, calling the checker as few times as possible.
Example 1:
Input: n = 5, checker answers = [good, good, good, bad, bad]
Output: 4
Explanation: The checker answers [false, false, false, true, true] for versions 1..5, so version 4 is where things first broke.
Example 2:
Input: n = 1, checker answers = [bad]
Output: 1
Explanation: There is only one version and it is bad, so the answer is 1.
Constraints:
- 1 ≤ first bad version ≤ n ≤ 2³¹ - 1
- At least one bad version always exists.
- The checker's answers are monotone: once it says bad, it says bad for every later version.
Hints:
Write out the checker's answers for versions 1..n: they form a block of 'good' followed by a block of 'bad'. You are looking for the boundary between the two blocks.
A monotone yes/no sequence is exactly what binary search eats: if is_bad(mid) is true, the boundary is at mid or to its left; if false, it is strictly to the right. Shrink [lo, hi] until one candidate remains — about log2(n) checker calls.
With n as large as 2^31 - 1, compute the midpoint as lo + (hi - lo) / 2 (or use a 64-bit type) so the addition cannot overflow.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 5, checker answers = [good, good, good, bad, bad]
Expected output: 4