Binary Search Basics

Description

Finding a value in a list of n items means looking at up to n of them, unless the list is sorted. Then one comparison with the middle element tells you which half can't contain the value, and halving 30 times narrows a billion items to one. The idea is simple. The details are where most binary searches go wrong: the loop condition, the updates, duplicates and overflow. This skill makes those details automatic, and covers the sorting that binary search depends on.

We'll go from simple to more technical:

1. The pattern: halve the range, with the loop condition matched to the updates.
2. A second flavor: lower bound, the first position that qualifies.
3. Where binary search runs in production (indexes, version bisecting, lookups).
4. What breaks it: unsorted input, mismatched loops, duplicates, overflow.

The approach

int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;              // the target, if present, is in [lo, hi]
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;              // never (lo + hi) / 2: the sum can overflow
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) lo = mid + 1;      // mid and everything left of it are too small
        else hi = mid - 1;                         // mid and everything right of it are too big
    }
    return -1;
}

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1                      # the target, if present, is in [lo, hi]
    while lo <= hi:
        mid = (lo + hi) // 2                       # Python ints can't overflow; // keeps it an int
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1                           # mid and everything left of it are too small
        else:
            hi = mid - 1                           # mid and everything right of it are too big
    return -1

The loop keeps one promise: if the target exists, it's inside [lo, hi]. Every update removes only positions proven wrong, and mid itself is always removed, so the range shrinks every step and the loop ends. It's O(log n) - about 30 steps for a billion items - but only because the array is sorted. On unsorted data nothing fails loudly: the comparison discards the wrong half and the search quietly reports "not found".

A second flavor: the first position that qualifies

With duplicates, "find the target" has several right answers, and questions usually want a specific one - the first occurrence, the last, or where to insert. Lower bound finds the first index whose value is >= x, using a half-open range whose meaning is "the answer is in [lo, hi]", where hi = n means "nowhere":

int lowerBound(int[] nums, int x) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {                              // lo == hi: the range has one candidate left
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < x) lo = mid + 1;           // mid is too small - the answer is after it
        else hi = mid;                             // mid might be the answer - keep it
    }
    return lo;
}
// first occurrence: lowerBound(x) (check nums[it] == x); last occurrence: lowerBound(x + 1) - 1

def lower_bound(nums: list[int], x: int) -> int:
    lo, hi = 0, len(nums)
    while lo < hi:                                 # lo == hi: the range has one candidate left
        mid = (lo + hi) // 2
        if nums[mid] < x:
            lo = mid + 1                           # mid is too small - the answer is after it
        else:
            hi = mid                               # mid might be the answer - keep it
    return lo

# the standard library has both bounds: bisect.bisect_left(nums, x) (first >= x), bisect.bisect_right(nums, x) (first > x)

The loop condition must match the updates: with hi = mid (mid kept), the loop has to be lo < hi; with lo <= hi it can sit on lo == hi == mid forever. The same "find where a condition flips" shape handles rotated arrays (one half is always sorted - check which, then whether the target lies in it) and index properties (in a sorted array of pairs with one single element, pairs before the single start at even indices).

Where you'll see it

Database indexes (B-trees) and sorted files use the same halving at every node or block; git bisect binary-searches commit history for the change that introduced a bug; time-series stores find a time range with lower and upper bounds; standard libraries expose it directly (Arrays.binarySearch, Collections.binarySearch, C++'s lower_bound, Python's bisect.bisect_left and bisect_right).

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. What happens if binary search runs on an unsorted array?

2. A lower-bound loop uses while (lo <= hi) with hi = mid. What goes wrong?

3. How do you get the first and last index of a target in a sorted array with duplicates?

Key takeaways

• Binary search keeps one promise - "if it's there, it's in [lo, hi]" - and removes only positions proven wrong.
• It needs sorted data (or any monotonic condition); on unsorted data it fails silently.
• Match the loop condition to the updates: lo <= hi with mid ± 1, lo < hi with hi = mid.
• Lower bound (first >= x) and upper bound (first > x) handle duplicates, first/last occurrence and insertion points.
• Use lo + (hi - lo) / 2 for the midpoint.