First Bad Version

You are given $N$ versions of a software product [1, 2, ..., N]. If a version is bad, all subsequent versions are also bad. You have a helper function is_bad_version(version) that returns True if a version is bad and False if it is good. Write a function to find the first bad version while minimizing the number of API calls. Constraint: You must achieve $O(\log N)$ time complexity.

Since the versions go from all "good" to all "bad" at a specific point, the results of is_bad_version look like a sorted boolean array (e.g., [False, False, True, True, True]). Because this sequence is strictly ordered, we can apply Binary Search to find the exact boundary where False turns to True, effectively cutting the search space in half with every check.

1. Initialize two pointers: first_version = 1 and last_version = n to represent the search space.
2. Run a while loop as long as first_version < last_version.
3. Calculate the mid point.
4. Call the API: is_bad_version(mid).
5. If it returns True, the first bad version is either this mid version or something before it. Narrow the search to the left half by setting last_version = mid.
6. If it returns False, the current version is good, meaning the first bad version must be strictly after it. Narrow the search to the right half by setting first_version = mid + 1.
7. When the two pointers meet, they will land exactly on the first bad version.

• Setting last_version = mid - 1 when is_bad_version(mid) is True. If mid happens to be the very first bad version, subtracting 1 completely removes the correct answer from the search space.
• Using a standard Binary Search while first_version <= last_version condition, which can easily lead to an infinite loop when shifting boundaries without +1 or -1. Using < guarantees termination when they meet.
• Integer overflow in other languages: While Python handles arbitrarily large integers, in languages like Java or C++, (left + right) / 2 can cause an overflow error. The safer formula is left + (right - left) / 2.

This pattern is known as "Binary Search for a Boundary" or "Binary Search on an Answer." It is incredibly versatile and appears constantly in systems engineering, such as finding the exact commit where a bug was introduced (which is exactly how the git bisect command works under the hood).