First Bad Version

Try It Yourself

Use the editor below to find the boundary where good versions become bad. In this runner, firstBad represents the external version-check API used by the original problem.

Submit your implementation when it passes the examples. The first bad version may be the first or last version in a very large range.

First Bad Version

easyBinary Search · Boundaries20 minLC 278

Problem

Versions are numbered from 1 through n. Once a version is bad, every later version is also bad.

Given n and firstBad, return the first bad version. The firstBad parameter replaces LeetCode's external isBadVersion API in this exercise.

Example 1:

Input: n = 5, firstBad = 4

Output: 4

Example 2:

Input: n = 1, firstBad = 1

Output: 1

Constraints

1 ≤ firstBad ≤ n ≤ 2³¹ - 1
Minimize the number of version checks.

0 attempts

Keep a search range that is guaranteed to contain the first bad version. If the middle version is bad, it may be the answer, so keep it and discard only later versions. If it is good, discard it and everything earlier.

The boundaries meet at the first version for which the bad-version condition is true.

function firstBadVersion(n, firstBad) {
  let left = 1;
  let right = n;

  while (left < right) {
    const middle = left + Math.floor((right - left) / 2);

    if (middle >= firstBad) right = middle;
    else left = middle + 1;
  }

  return left;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(log n)`	Each version check halves the remaining range.
Auxiliary space	`O(1)`	The search uses only boundary and middle integers.

First Bad Version

Try It Yourself

Example 1:

Example 2:

Constraints

Solution

Big O notation