First Bad Version Solutions & Complexity

1. Define the problem

First Bad Version

You are a product manager and currently leading a team to develop a new product. Versions 1 through n of the product were built in order, and at some point a bad version corrupted every version after it. You are given an API isBadVersion(version) that returns whether version is bad. Implement a function to find the first bad version and minimize the number of calls to the API. This is a boundary search over a sequence that is good, good, ..., bad, bad — narrow low and high toward the first bad one.

Constraints

1 ≤ bad ≤ n ≤ 2³¹ - 1

Example

Inputn = 5, bad = 4

Output4

Explanation Versions 1, 2, 3 are good and versions 4, 5 are bad — the first bad version is 4.

2. Know the words first

In plain terms

First bad version: Once a version is bad, every later version is bad too — the goal is to find the exact point where "good" turns into "bad".

3. Visualize the solution

Binary search over versions for the first bad one

1good

2good

3good

4bad

5bad

Statusinit

low=1, high=5, mid=3 (version 3, good). low moves to 4.

What happens in this step

low=1, high=5
mid = 1 + floor((5-1)/2) = 3, version 3 is good

isBadVersion(3) is false, so the boundary is strictly after mid — low becomes 4.

Step 1 of 3

Steps to visualize

The row is all five versions; the box marks the versions still in doubt.
Start low at 1 and high at n.
While low < high, check the version at mid.
If mid is bad, the boundary is at or before mid, so high = mid.
If mid is good, the boundary is strictly after mid, so low = mid + 1.
When low === high, that version is the first bad one.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Binary search over versions for the first bad one

1good

2good

3good

4bad

5bad

Statusinit

low=1, high=5, mid=3 (version 3, good). low moves to 4.

What happens in this step

low=1, high=5
mid = 1 + floor((5-1)/2) = 3, version 3 is good

isBadVersion(3) is false, so the boundary is strictly after mid — low becomes 4.

Step 1 of 3

5. Solution

Solution

solution.tsTypeScript

function firstBadVersion(n, firstBad) {
  const isBadVersion = (version) => version >= firstBad;

  let low = 1;
  let high = n;

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);

    if (isBadVersion(mid)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

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

6. Test cases

Test cases

Input	Expected	Covers
`n = 5, bad = 4`	`4`	example from the docstring
`n = 5, bad = 1`	`1`	the very first version is already bad
`n = 5, bad = 5`	`5`	only the last version is bad
`n = 1, bad = 1`	`1`	smallest valid input, one version which is bad
`n = 2, bad = 2`	`2`	boundary case with exactly two versions
`n = 2126753390, bad = 1702766719`	`1702766719`	large n exercising the log n call budget
`n = 10, bad = 6`	`6`	boundary sitting in the middle of the range

First Bad Version