First Bad Version LeetCode Solution — Binary Search Boundary

LeetCode #278 First Bad Version is one of those rare problems that maps directly to a tool you probably already use. If you have ever run git bisect to find the commit that broke your build, you have already solved this problem — you just did not know it had a LeetCode number.

The setup is simple: you have n versions of a product numbered 1 through n. At some point one version went bad, and every version after it is also bad. Your job is to find the first bad version using as few API calls as possible.

This is a pure binary search problem, but the specific variant it teaches — the "find first true" template — is one of the most reusable patterns in all of algorithm design. Once you internalize it here, you will recognize it everywhere.

You are given an API function isBadVersion(version) that returns true if the given version is bad and false otherwise. The versions form a clean boundary: all versions before the first bad one return false, and all versions from the first bad one onward return true.

Think of it as a sorted boolean array: [false, false, false, true, true, true]. You need to find the index of the first true. The constraint is that you want to minimize the number of calls to isBadVersion, which means brute-forcing from version 1 is out — that would be O(n) calls.

The key insight is that this sorted structure is exactly what binary search exploits. You can cut the search space in half with each API call, bringing the total down to O(log n).

The search space is [1, n]. At each step you check the middle version. If isBadVersion(mid) returns true, the first bad version is mid or somewhere to its left, so you set right = mid. If it returns false, the first bad version must be to the right, so you set left = mid + 1.

When the loop ends, left and right have converged to the same index — that is your answer. The reason this works is that the loop maintains an invariant: the first bad version is always within [left, right].

This is the classic "find first true" binary search template. It differs from the standard "find target" template in two ways: you use left < right instead of left <= right, and you set right = mid instead of right = mid - 1. These two changes make the pointers converge on the boundary rather than overshooting it.

The implementation is concise. Initialize left = 1 and right = n. While left < right, compute mid = left + Math.floor((right - left) / 2). If isBadVersion(mid) is true, set right = mid. Otherwise set left = mid + 1. When the loop exits, return left.

The time complexity is O(log n) since you halve the search space with each call. The space complexity is O(1) — you only need two pointers. For n up to 2^31 - 1 (the maximum given in the constraints), that means at most 31 API calls.

One subtle but critical detail is how you compute mid. Using (left + right) / 2 can overflow when both values are large integers. The safe formula is left + (right - left) / 2, which produces the same result without the risk of exceeding integer bounds.

Let us trace through an example with n = 5 and the first bad version = 4. The versions look like [good, good, good, bad, bad].

Iteration 1: left = 1, right = 5, mid = 3. isBadVersion(3) returns false, so the first bad version is after 3. Set left = 4.

Iteration 2: left = 4, right = 5, mid = 4. isBadVersion(4) returns true, so the first bad version is 4 or earlier. Set right = 4.

Now left == right == 4, so the loop exits. Return 4 — the first bad version. We used only 2 API calls instead of the 4 that a linear scan would require.

The first edge case is when the very first version is bad. With left = 1 and right = n, mid starts around n/2. Since every version is bad, isBadVersion always returns true, and right keeps shrinking until both pointers land on 1.

The second edge case is when only the last version is bad. Here isBadVersion returns false for everything except n, so left keeps advancing rightward until both pointers converge on n.

The third edge case is n = 1 — there is only one version and it must be bad. The loop condition left < right is immediately false (both are 1), so you return 1 without making any API calls.

First Bad Version is the cleanest example of the "find first true" binary search template. This template reappears in Search Insert Position (#35) where you find the first index where a value could be inserted, in Sqrt(x) (#69) where you find the boundary between valid and invalid square roots, and in dozens of other problems.

The real-world connection to git bisect makes this problem especially valuable. When you debug a regression in production by bisecting commits, you are running exactly this algorithm. Understanding it here means you understand the theory behind one of your most practical debugging tools.

Practice this pattern until the template is automatic — left < right, right = mid, left = mid + 1, return left. YeetCode flashcards help you drill this specific template so it becomes second nature before your next interview.