First Bad Version

Easy· binary search· predicate search

Problem

Versions 1 through n of a product were released, and once a version is bad every later version is bad too. You can call isBadVersion(v) to check any version. Find the first bad version while making as few calls as possible.

Examples

Input: n = 6, first bad = 3

Output: 3

Versions 1-2 are good and 3-6 are bad, so 3 is the boundary.

Input: n = 1, first bad = 1

Output: 1

Constraints

• 1 <= bad <= n <= 2^31 - 1

Hints & approach

Hint 1

The results of isBadVersion form a pattern like good, good, bad, bad, bad.

Hint 2

Binary search for the first true in a monotonic boolean sequence.

Hint 3

Be careful computing mid when n is close to the integer limit.

Approachtry the hints first

The predicate isBadVersion is monotonic: false up to some point, then true forever. Binary search for the first true with lo = 1, hi = n. If mid is bad, the answer is mid or earlier, so hi = mid; otherwise lo = mid + 1. When lo meets hi it points at the first bad version. Compute mid as lo + (hi - lo) / 2 to avoid overflow.

Time O(log n) · Space O(1)

← PreviousSearch Insert Position Next →Find First and Last Position of Element in Sorted Array