Binary Search: The O(log n) Template Every Variant Builds On

Binary search has a strange reputation: everyone can explain it in one sentence, and almost nobody writes it correctly on the first try. Jon Bentley reported in Programming Pearls that when he asked professional programmers to implement it, roughly 90% got it wrong — and a subtle overflow bug sat inside Java's own standard-library binarySearch for nine years before anyone noticed.

The idea itself is the cleanest in all of algorithms: if the data is sorted, one comparison can eliminate half of it. That single sentence turns a million-element search into about 20 comparisons, and a billion-element search into about 30.

This problem anchors an entire interview topic because of the template. Get the loop condition, the midpoint, and the pointer updates right once, and every variant — rotated arrays, boundary searches, guessing games — is the same skeleton with one line changed.

The problem#

Given a sorted integer array nums and an integer target, return the index of target if it exists, otherwise return -1.

Two words in the statement do all the work:

• Sorted — this is the license to discard half the array per comparison. Without it, binary search is simply wrong.
• Index — you return a position, so the algorithm tracks a window of candidate indices, not values.

LeetCode also states the values are distinct, which means there's at most one valid index — no ambiguity about which occurrence to return.

The brute force baseline#

Ignore the sorted property and you get a linear scan:

This is O(n): a miss inspects every element, and even hits average n/2 comparisons. It isn't wrong — but it throws away the one guarantee the problem hands you. When nums[i] is smaller than the target, sortedness says everything left of i is also smaller; the linear scan learns that and does nothing with it. Interviewers expect you to name this baseline in a sentence and immediately reach for the sorted structure.

The key insight: shrink a window, don't scan a list#

Reframe the search as maintaining a window [left, right] that is guaranteed to contain the target if it exists anywhere. That guarantee is the loop invariant, and everything else falls out of protecting it.

Probe the middle element nums[mid]. Sortedness makes one comparison answer for half the window:

• nums[mid] === target → done, return mid.
• nums[mid] < target → the target can't be at mid or anywhere left of it (those are all ≤ nums[mid]). The window becomes [mid + 1, right].
• nums[mid] > target → mirror argument. The window becomes [left, mid - 1].

Every iteration either returns or throws away at least half of the remaining window — including mid itself, which is what keeps the window strictly shrinking. When left crosses right, the window is empty, and the invariant says the target was never there: return -1.

This is the binary search pattern: a search over a monotonic space where each probe kills half the candidates. The "space" here happens to be array indices, but nothing in the reasoning requires an array — which is exactly why the pattern generalizes so far.

The optimal solution#

Three decisions in this template are load-bearing, and they must agree with each other:

• Inclusive bounds: right = nums.length - 1 means both endpoints are candidates. That convention requires left <= right, because a one-element window has left === right and still needs one final probe.
• mid ± 1 updates: mid has already been compared, so it must leave the window. Writing left = mid instead can loop forever on a two-element window, where Math.floor keeps landing mid on left.
• Math.floor((left + right) / 2): safe in JavaScript because numbers are 64-bit floats and array indices can't get near the precision limit. In Java or C++, left + right can overflow a 32-bit int — that was the standard-library bug — so those languages write left + (right - left) / 2.

You can step through this exact code interactively and watch the window collapse pointer by pointer.

Walkthrough: nums = [-1, 0, 3, 5, 9, 12], target = 9#

Two comparisons for a six-element array. Step 1 is the pattern in miniature: one probe at index 2 proved that indices 0–2 are all too small, so half the array vanished without ever being read.

The miss case matters just as much. Same array, target = 2:

Step 3 is why the loop condition is <=: the window has shrunk to the single index 1, and that element still deserves a look. With left < right, the loop would exit before probing it — and if the target had been 0, you'd have returned -1 for a value sitting right there.

Complexity#

The window starts at n elements and at least halves every iteration, so it empties after at most ⌈log₂ n⌉ + 1 probes. Concretely: n = 1,000,000 → at most 20 comparisons; n = 10⁹ → 30. The gap between n and log n is the biggest speedup you'll ever buy with one observation about the input.

Common mistakes#

• while (left < right) with inclusive bounds. Drops the final one-element window, as the miss walkthrough shows. right = nums.length - 1 pairs with <= — always.
• left = mid or right = mid instead of mid ± 1. mid is already judged; keeping it in the window can stall the shrink and spin forever on two-element windows.
• Mixing conventions. right = nums.length (exclusive) with left <= right reads one past the end; right = nums.length - 1 with left < right skips the last probe. Pick the closed-interval template above and keep all three lines consistent.
• (left + right) / 2 in fixed-int languages. Overflows once left + right exceeds 2³¹ − 1. Fine in JavaScript, a real bug in Java/C++/Go — write left + (right - left) / 2 there.
• Running it on unsorted input. Binary search on unsorted data doesn't fail loudly; it confidently returns wrong answers. If sortedness isn't stated, it isn't there.
• Forgetting Math.floor. In JavaScript, (left + right) / 2 produces fractions like 2.5, and nums[2.5] is undefined — every comparison against it is false and the loop misbehaves.

Where this pattern shows up next#

Everything in the binary search topic is this template with one line rewritten:

• Sqrt(x) — binary search over the answer space instead of an array: find the largest mid with mid * mid <= x.
• Guess Number Higher or Lower — the comparison becomes an API call; the halving logic is untouched.
• First Bad Version — a boundary search: instead of finding an exact match, find the leftmost true, which changes the update to right = mid.
• Search in Rotated Sorted Array — the array is bent, but one half is always sorted; detecting which half restores the discard step.

Nail the invariant here — the window always contains the answer if it exists — and each of those becomes a five-minute delta instead of a new algorithm.

FAQ#

Why is binary search O(log n)?#

Each iteration compares the target against the middle of the current window and discards at least half of it, including the probed element. A window of n elements can only be halved about log₂ n times before it's empty, so the loop runs at most ⌈log₂ n⌉ + 1 times, each doing O(1) work. For a million elements that's at most 20 comparisons; for a billion, 30.

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

Because the template uses inclusive bounds — right starts at nums.length - 1, so both endpoints are valid candidates. When the window shrinks to a single element, left === right, and that element still needs to be checked. With left < right the loop exits one probe early and misses targets that sit exactly at the final index. If you prefer left < right, you must switch to an exclusive right bound (right = nums.length) and adjust the updates to match — mixing the two conventions is the classic off-by-one.

Do I need to worry about integer overflow in the mid calculation?#

Not in JavaScript: numbers are 64-bit floats, and left + right for any realistic array length stays far below the 2⁵³ precision limit. In languages with 32-bit ints — Java, C++, C#, Go — left + right can overflow when both are large, which is exactly the bug that lived in java.util.Arrays.binarySearch for years. The portable fix is mid = left + (right - left) / 2, which never exceeds right.

Does binary search work if the array has duplicates?#

The classic template still terminates and still returns a valid index when the target exists — it just makes no promise about which occurrence you get, because the probe can land on any copy. If you need the leftmost or rightmost occurrence, you switch to a boundary-search variant that keeps searching after a match instead of returning immediately. The LeetCode Binary Search problem sidesteps this by guaranteeing distinct values.

Does the array have to be sorted for binary search?#

Yes — sortedness is the entire justification for discarding half the window after one comparison. On unsorted data the discarded half can silently contain the target, and the algorithm returns -1 or a wrong index with no error. The requirement generalizes, though: any monotonic condition works, which is how the same template searches answer ranges in Sqrt(x) or version histories in First Bad Version.