First Bad Version

Explanation & Solution

Description

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 version, all versions after a bad version are also bad.

Given n versions [1, 2, ..., n], find the first bad version which causes all the following ones to be bad.

You are given an API isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version, minimizing the number of API calls.

In this implementation, you receive n and bad (the first bad version) as parameters.

Input: n = 5, bad = 4

Output: 4

Explanation: isBadVersion(3) = false, isBadVersion(4) = true, isBadVersion(5) = true. So 4 is the first bad version.

Constraints

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

Approach

Modified Binary Search pattern

1. Define the Search Space

Set lo = 1 and hi = n to search over all versions.

2. Binary Search

Compute mid = lo + ((hi - lo) >> 1) to avoid overflow.
Call isBadVersion(mid).

3. Narrow the Range

If mid is bad, the first bad version is at mid or earlier → hi = mid.
If mid is good, the first bad version is after mid → lo = mid + 1.

4. Return the Answer

When lo === hi, we've found the first bad version.

🧠 Key Insight

This is a textbook binary search on a boolean predicate: all versions before the answer are good, all from the answer onward are bad.

Time

O(log n)classic binary search.

Space

O(1).

Solution Code

Find Peak Element

Search a 2D Matrix