Data Structures & Algorithms · Binary Search

First Bad Version: The Leftmost-True Binary Search Template

Q: Why is the loop condition left < right instead of left <= right?

Because the loop's goal is to shrink the range [left, right] to a single candidate, not to detect a match. Once left === right, the invariant — the range always contains the first bad version — guarantees that lone candidate is the answer. Using left <= right here is actively dangerous: combined with right = mid, an iteration where left === right === mid and mid is bad makes no progress, and the loop spins forever.

Q: Why does the solution set right = mid instead of right = mid - 1?

When isBadVersion(mid) returns true, mid itself might be the first bad version — you only know the answer is at mid or earlier. Setting right = mid - 1 throws away a live candidate and can converge past the answer. The asymmetry is the heart of the template: bad mids are kept (right = mid), good mids are fully discarded (left = mid + 1), because only a good version can never be the answer.

Q: What is the time complexity of First Bad Version?

O(log n) API calls and O(1) space. Each iteration makes exactly one isBadVersion call and halves the search range, so n = 2,147,483,647 versions resolve in at most 31 calls. The linear scan costs O(n) calls — up to about two billion at that constraint — which is why the problem explicitly asks you to minimize API calls.

Q: Can (left + right) / 2 overflow?

Not in JavaScript: numbers are 64-bit floats exact up to 2⁵³, and left + right stays below 2³² even at the maximum constraint. In languages with 32-bit ints — Java, C++, Go — left + right can overflow when n is near INT_MAX, producing a negative mid. The portable habit is left + (right - left) / 2, which computes the same midpoint without ever exceeding right.

Q: Why is the JavaScript solution a function that returns a function?

That's LeetCode's harness design, not part of the algorithm. The judge calls solution(isBadVersion) once to inject the API, and the returned inner function (n) => ... is what runs per test case. The closure gives the inner function access to isBadVersion without a global; all the binary search logic lives inside it.

First Bad Version solved with left-boundary binary search: why right = mid keeps the answer, a worked walkthrough, JavaScript code, and complexity analysis.

July 12, 20267 min readBy Bhavesh Singh

binary searchleft boundary binary searchleftmost trueboundary searchleetcode easy

This article has an interactive companion

Don't just read it — step through it interactively, one state change at a time.

Open the First Bad Version visualizer

First Bad Version is the problem that quietly upgrades your binary search. The classic version hunts for an exact value in a sorted array. This one asks for something subtly different — and far more reusable: find the boundary where a condition flips from false to true. No target value, no array, just a yes/no oracle and a range of candidates.

The story is concrete: your product's versions build on each other, a bug shipped somewhere, and every version after the buggy one is also broken. You get one tool — isBadVersion(version) — and it's expensive to call, like kicking off a full CI build. Find the first bad version with as few calls as possible.

The template here — left boundary binary search, also called "leftmost true" or lower bound — is the same skeleton behind Sqrt(x), Koko Eating Bananas, and every "binary search on the answer" problem. Get its two update rules right once and you'll never fumble an off-by-one in this family again.

The problem

You have n versions numbered 1 through n. Each version is built on the previous one, so once a version is bad, every later version is also bad. You're given an API isBadVersion(version) that returns true or false. Return the first bad version, minimizing the number of API calls.

text

Input:  n = 5, first bad version = 4
        isBadVersion(3) → false
        isBadVersion(4) → true
Output: 4

Two facts in that statement do all the work:

The versions are monotonic: good, good, ..., good, bad, bad, ..., bad. Once bad, always bad. That ordering makes binary search legal even though there's no array of numbers anywhere.
The API is expensive, so the metric that matters isn't loop iterations — it's the count of isBadVersion calls.

The brute force baseline

Walk forward from version 1 and return the first version that fails:

javascript

var solution = function(isBadVersion) {
  return function(n) {
    for (let v = 1; v <= n; v++) {
      if (isBadVersion(v)) return v;
    }
    return n;
  };
};

Correct, and O(n) API calls. That's fatal here: the classic constraint allows n up to 2,147,483,647, so a bad version near the end costs roughly two billion calls. If each call were a one-second build check, the scan runs for about 68 years. Binary search answers the same question in at most 31 calls.

The key insight: search for the boundary, not a value

Squint at the versions as a boolean sequence and the shape appears immediately:

text

version:  1  2  3  4  5
isBad:    F  F  F  T  T
                   ↑
             first bad = leftmost T

You're not looking for a value that equals some target. You're looking for the leftmost true — the exact point where false flips to true. Monotonicity guarantees exactly one flip point, so every isBadVersion(mid) answer eliminates half the range:

Mid is bad → the first bad version is mid or something earlier. You cannot discard mid — it might be the answer. Shrink the right edge onto it: right = mid.
Mid is good → the first bad version is strictly after mid. Discard mid and everything before it: left = mid + 1.

These asymmetric updates maintain one invariant: the range [left, right] always contains the first bad version. Keep halving while left < right; when the pointers meet, the invariant says the lone survivor is the answer — no final verification call needed.

Note what's missing compared to classic binary search: no return mid inside the loop, no right = mid - 1 on a hit. Finding a bad version isn't success — finding the earliest one is.

The optimal solution

This is the exact algorithm the First Bad Version visualizer steps through:

javascript

var solution = function(isBadVersion) {
  return function(n) {
    let left = 1, right = n;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (isBadVersion(mid)) right = mid;
      else left = mid + 1;
    }
    return left;
  };
};

The curried shape (solution takes the API and returns the real function) is just LeetCode's harness injecting isBadVersion — the algorithm is the inner function.

Three choices in that loop are load-bearing:

right = mid, not mid - 1. A bad mid is a live candidate; stepping past it can skip the answer.
left = mid + 1. A good mid can never be the answer, so discard it fully — this is also what guarantees the range shrinks every iteration.
while (left < right), no equals. The loop's job is to collapse the range to one version. Once left === right there's nothing left to ask.

Exactly one API call per iteration, and each iteration halves the range: that's the minimal-calls guarantee the problem asks for.

Walkthrough: n = 5, first bad version = 4

Step	left	right	mid	isBadVersion(mid)	Action
1	1	5	3	false (good)	answer is after 3 → left = 4
2	4	5	4	true (bad)	4 may be the answer → right = 4
3	4	4	—	—	left === right → return 4

Step 2 separates this template from vanilla binary search. Mid = 4 is bad, but the algorithm doesn't return — an earlier bad version could still exist, so it sets right = 4 and keeps the candidate alive. The pointers have now met, the range has collapsed, and the invariant hands you the answer.

Total cost: 2 API calls. The linear scan on the same input makes 4.

Complexity

Approach	Time (API calls)	Space	Why
Linear scan	O(n)	O(1)	checks every version until the first bad one
Left boundary binary search	O(log n)	O(1)	one call per iteration, range halves each time

At the maximum constraint of n = 2,147,483,647, binary search needs at most 31 calls — ⌈log₂(n)⌉ — versus up to ~2.1 billion for the scan. Space is constant either way: two pointers and a mid.

Common mistakes

Setting right = mid - 1 when mid is bad. The single most common bug. The first bad version might be mid; stepping past it converges one slot too far right on some inputs.
Writing while (left <= right) with right = mid. When left === right === mid and mid is bad, right = mid changes nothing and the loop never exits. The < condition and right = mid are a package deal.
Computing mid as (left + right) / 2 in fixed-width languages. Safe in JavaScript (64-bit floats; left + right tops out near 2³²), but in Java, C++, or Go it overflows a 32-bit int when n is near INT_MAX. The portable form is left + (right - left) / 2.
Returning mid from inside the loop. There is no "found it" moment here. A true from the API only narrows the range; the collapsed range identifies the first bad version.
Calling isBadVersion(mid) more than once per iteration. Each call is expensive by construction; if you need the result twice, cache it in a const.
Starting left at 0. Versions are 1-indexed. This off-by-one only surfaces when version 1 itself is bad.

Where this pattern shows up next

The leftmost-true template is one of the binary search variants worth having in muscle memory:

Binary Search — the exact-match classic, where return mid inside the loop is correct. Contrast the two and the boundary variant clicks.
Guess Number Higher or Lower — the same expensive-oracle setup, with three-way feedback instead of a boolean.
Sqrt(x) — boundary search over answers instead of indices: find the last k where k² ≤ x, the mirror-image "rightmost true".
Search in Rotated Sorted Array — invariant-driven half elimination when the input isn't even fully sorted.

You can also step through First Bad Version interactively and watch the range collapse onto the boundary, one API call at a time.

FAQ

Why is the loop condition left < right instead of left <= right?

Because the loop's goal is to shrink the range [left, right] to a single candidate, not to detect a match. Once left === right, the invariant — the range always contains the first bad version — guarantees that lone candidate is the answer. Using left <= right here is actively dangerous: combined with right = mid, an iteration where left === right === mid and mid is bad makes no progress, and the loop spins forever.

Why does the solution set right = mid instead of right = mid - 1?

When isBadVersion(mid) returns true, mid itself might be the first bad version — you only know the answer is at mid or earlier. Setting right = mid - 1 throws away a live candidate and can converge past the answer. The asymmetry is the heart of the template: bad mids are kept (right = mid), good mids are fully discarded (left = mid + 1), because only a good version can never be the answer.

What is the time complexity of First Bad Version?

O(log n) API calls and O(1) space. Each iteration makes exactly one isBadVersion call and halves the search range, so n = 2,147,483,647 versions resolve in at most 31 calls. The linear scan costs O(n) calls — up to about two billion at that constraint — which is why the problem explicitly asks you to minimize API calls.

Can (left + right) / 2 overflow?

Not in JavaScript: numbers are 64-bit floats exact up to 2⁵³, and left + right stays below 2³² even at the maximum constraint. In languages with 32-bit ints — Java, C++, Go — left + right can overflow when n is near INT_MAX, producing a negative mid. The portable habit is left + (right - left) / 2, which computes the same midpoint without ever exceeding right.

Why is the JavaScript solution a function that returns a function?

That's LeetCode's harness design, not part of the algorithm. The judge calls solution(isBadVersion) once to inject the API, and the returned inner function (n) => ... is what runs per test case. The closure gives the inner function access to isBadVersion without a global; all the binary search logic lives inside it.

Make it stick: run this one yourself

Don't just read it — step through it interactively, one state change at a time.

Open the First Bad Version visualizer

The problem#

The brute force baseline#

The key insight: search for the boundary, not a value#

The optimal solution#

Walkthrough: n = 5, first bad version = 4#

Complexity#

Common mistakes#

Where this pattern shows up next#

FAQ#

Why is the loop condition left < right instead of left <= right?#

Why does the solution set right = mid instead of right = mid - 1?#

What is the time complexity of First Bad Version?#

Can (left + right) / 2 overflow?#

Why is the JavaScript solution a function that returns a function?#

Related articles