DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

First Bad Version

easyBinary search Must-do

Problem statement

Versions 1 to n were released in order, and at some point one version introduced a bug, so it and every later version are bad. Using an isBadVersion(version) API, find the first bad version with as few calls as possible.

Examples

Example 1

Input: n = 5, first bad version = 4

Output: 4

Explanation: isBadVersion(3) is False and isBadVersion(4) is True, so 4 is the first bad version.

Approach

Optimal

The versions look like good, good, good, bad, bad: a sorted list of booleans. Checking one by one could take n calls. Binary search halves the range each time: test the middle version; if it's bad, the first bad one is there or earlier; if it's good, it must be later. That's about 30 calls even for a billion versions.

  1. Keep a search range: low = 1, high = n.
  2. While low < high, check the middle version mid = low + (high - low) // 2.
  3. If mid is bad, the answer is mid or earlier: set high = mid. If it's good, the answer is later: set low = mid + 1.
  4. When low meets high, that version is the first bad one.
ComplexityTime O(log n)Space O(1)
Python
def first_bad_version(n: int) -> int:
low, high = 1, n
while low < high:
mid = low + (high - low) // 2
if is_bad_version(mid): # provided by the problem
high = mid # mid might be the first bad one
else:
low = mid + 1 # first bad one is after mid
return low

Frequently asked questions

This is literally what git bisect does to find the commit that broke a build, and how SREs find the deploy that caused a latency regression: test the midpoint between the last good and first known bad release, then halve. Being able to explain that link in an interview shows you understand why the algorithm matters, not just how to write it.

  • Setting high = mid - 1 when mid is bad, which can skip past the first bad version.
  • Computing (low + high) // 2 in languages with fixed-size integers, where it can overflow. low + (high - low) // 2 is safe everywhere.
  • Using while low <= high with these updates, which loops forever when low equals high.