4.11.1 — Binary Search

LeetCode 704 · Easy

The problem

Find target in a sorted array and return its index, or −1 if it is not there. Must be O(\log n).

nums = [-1,0,3,5,9,12], target = 9   →  4
nums = [-1,0,3,5,9,12], target = 2   →  -1

All values are distinct.

The pattern

Look at the middle. If it is the target, done. If it is too small, the answer must be to the right, so throw away the left half. If it is too big, throw away the right half. Repeat.

Each step halves what is left, so the number of steps is \log_2 n. For a million elements that is 20 comparisons.

The algorithm is trivial. Getting the boundaries right is not, and that is what the rest of this page is about — because every problem after this one depends on writing it without hesitation.

The solution

Python

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low, high = 0, len(nums) - 1

        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                low = mid + 1
            else:
                high = mid - 1

        return -1

TypeScript

function search(nums: number[], target: number): number {
  let low = 0, high = nums.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;
}

Four decisions in that code, and each one has a reason.

high = len(nums) - 1, and the loop runs while low <= high. These two go together. high is a real index, so the range is inclusive at both ends, and a range of one element (low == high) still has to be examined. Using < instead would skip it.

mid = low + (high - low) // 2 rather than (low + high) // 2. The two are mathematically equal, but the second can overflow in a fixed-width integer language when both indices are near the maximum, wrapping to a negative number and crashing on the array access. This was a real bug in Java's standard library, found in 2006 after nine years. Python and JavaScript will not overflow here, but write it the safe way anyway — it costs nothing and it is what an interviewer is watching for.

low = mid + 1 and high = mid - 1, never low = mid. mid has already been checked, so it must be excluded. Leaving it in also creates an infinite loop, for the reason below.

The three-way comparison is explicit. Forgetting the == target branch means the search overshoots and returns −1 even when the value is present.

The infinite loop, and where it comes from

Integer division rounds down. So when the range shrinks to two elements, mid is always the left one.

If your code then does low = mid in some branch, low never changes, the range never shrinks, and the loop runs forever. That is the classic binary search hang, and the fix is either to always advance past mid, or to use a strict while low < high loop shape.

Your Report 4 recorded this as the asymmetry of floor division, and it is the single most common way binary search breaks.

Two loop shapes, and when to use each

Almost every binary search you write is one of these two. Knowing which you are in prevents most bugs.

Shape A — find an exact element.

low, high = 0, len(a) - 1       # both are real indices
while low <= high:              # a one-element range is still checked
    mid = low + (high - low) // 2
    if a[mid] == target: return mid
    if a[mid] < target: low = mid + 1
    else: high = mid - 1
return -1

Shape B — find a boundary. The first position where some condition becomes true, which is what almost every harder binary search problem actually wants.

low, high = 0, len(a)           # high is ONE PAST the end
while low < high:               # stop when the range is empty
    mid = low + (high - low) // 2
    if condition(mid): high = mid       # mid might be the answer — keep it
    else: low = mid + 1                 # mid is not — discard it
return low                              # low == high == the boundary

Report 4 called these the bucket model and the fence model, and the names are good ones. In shape A you are looking inside buckets, so high is a real index. In shape B you are looking at the fences between buckets — an array of n items has n+1 possible cut positions — so high is len(a), one past the end.

Shape B never returns −1 and never compares for equality. It converges on a position. That is what makes it the right tool for "the smallest value that works", which is every problem from 4.11.3 onwards.

Complexity

O(\log n) time, O(1) space.

The generalisation that matters

Binary search does not need an array. It needs a monotonic predicate — a yes/no question whose answer, once it flips from false to true, stays true.

"Is a[i] >= target" is one such question. So is "can Koko finish the bananas at speed s", and "is x * x >= n". Whenever you can phrase your problem as find the smallest value where this becomes true, you can binary search it, whether or not any array exists.

That move is called binary search on the answer, and it is what the rest of this chapter is built on.

Where this goes next

• Search Insert Position — shape B, returning where the target would go.
• First and Last Position of an Element — two shape-B searches, one for each boundary.
• bisect_left and bisect_right in Python, lower_bound and upper_bound in C++ — shape B, already written for you. Know what they return.

What the interviewer will push on

"Why low + (high - low) // 2?" Overflow safety. Mention the Java bug; it is a good, short, true story.

"Why <= and not <?" Because high is a real index and a one-element range must still be checked. Then explain that shape B uses < because high is one past the end.

"Where does the infinite loop come from?" Floor division makes mid equal low on a two-element range, so low = mid never advances.

"Write it recursively." Straightforward, and O(\log n) stack, which is fine. Iterative is still preferred.

One thing to volunteer: say which of the two shapes you are writing before you write it. That single sentence prevents the boundary mistakes that this problem exists to expose.

Next: 4.11.2 Search a 2D Matrix — the same search, on a grid that is secretly one array.