DSA problem
First Bad Version
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous one, all versions after a bad version are also bad.
You are given an API bool isBadVersion(version) that returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API. Given n versions [1, 2, ..., n], you want to find the smallest version such that isBadVersion(version) is true.
The structure of the problem maps directly to a binary search on a monotonic boolean predicate. The sequence isBadVersion(1), isBadVersion(2), ... looks like false, false, ..., false, true, true, ..., true — a sorted boolean array. The leftmost true is exactly the first bad version. So you can binary-search the boundary between the two regions, never calling the API more than ⌈log2 n⌉ times.
Keep two pointers lo = 1 and hi = n. While lo < hi, query isBadVersion(mid): if true, the first bad version is mid or earlier (hi = mid); if false, it must be after mid (lo = mid + 1). When the loop ends, lo == hi is the answer. Note the loop uses strict < and does not exclude mid when narrowing hi — that's the standard lower-bound form. Use mid = lo + (hi - lo) / 2 to guard against integer overflow when n approaches 2^31 - 1.
Examples
n = 5, bad = 44n = 1, bad = 11n = 2126753390, bad = 17027667191702766719Constraints
- 1 <= bad <= n <= 2^31 - 1
- The API isBadVersion(version) returns a boolean.
- All versions after a bad version are also bad.
- Minimize the number of calls to isBadVersion.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.