First Bad Version

easy binary search interactive

Problem

You're given an API isBadVersion(v) that returns true once and forever once the build broke. Among versions 1..n, return the first bad version while making as few API calls as possible.

Inputn = 8, first bad = 5

Output5

isBadVersion goes false, false, false, false, true, true, true, true — bisect for the boundary.

first bad version

def firstBadVersion(n):
    lo, hi = 1, n
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if isBadVersion(mid):
            hi = mid
        else:
            lo = mid + 1
    return lo

var solution = function (isBadVersion) {
  return function (n) {
    let lo = 1, hi = n;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (isBadVersion(mid)) hi = mid;
      else lo = mid + 1;
    }
    return lo;
  };
};

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
}

class Solution {
public:
    int firstBadVersion(int n) {
        int lo = 1, hi = n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (isBadVersion(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

Explanation

The versions form a "good, good, …, bad, bad, …" pattern: once a build breaks, it stays broken. That monotone shape is exactly what binary search loves, so we can find the first bad version in O(log n) calls instead of checking each one.

We keep a window [lo, hi] starting at [1, n]. At each step we test the middle version with isBadVersion(mid). If it is bad, the first bad version is at mid or earlier, so we set hi = mid (keeping mid as a candidate). If it is good, the breakage starts later, so lo = mid + 1.

Note mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2 — this avoids integer overflow when n is very large. When lo == hi, the window has pinned down the boundary and we return lo.

Example: n = 8, first bad version 5. We test 4 (good → lo = 5), then 6 (bad → hi = 6), then 5 (bad → hi = 5). Now lo == hi == 5, so the answer is 5.

Halving the range each call gives O(log n) API calls, the whole point of the problem.

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