Binary search

You’ll recognise it when

• The input is sorted, and you need to find a value or the spot where it would go.
• The question says first or last position where something becomes true.
• A linear scan would work, but n is 10⁵ or more and there are many queries.
• You want the smallest speed, capacity or time that still works, and bigger always works too. That’s binary search on the answer (see Variations).

The idea

Someone picks a number from 1 to 100 and answers each guess with “higher” or “lower”. You wouldn’t guess 1, 2, 3… You’d guess 50: whatever the reply, half the numbers are gone. Seven guesses always suffice, because 2⁷ = 128 is more than 100.

Binary search is that game on a sorted array. Look at the middle element. If it’s smaller than the target, the target can only be in the right half, so drop the left half. Otherwise drop the right half. Every look halves what’s left.

How it works

We’ll write the version that’s most useful in practice, lower bound: return the first index whose value is >= target. One loop answers both “where is it?” and “where would it go?”.

Scroll through the steps and the graphic follows along. You can also press play, step with the arrow keys, or edit the input: try duplicates, a missing value, or a target bigger than everything.

Why it’s correct: everything left of lo is always < target, and everything from hi on is always >= target. Each step keeps both facts true and shrinks the gap between them, so when the gap closes, lo sits exactly on the boundary.

def lower_bound(a, target):
    """First index i with a[i] >= target, or len(a) if there is none."""
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo


def search(a, target):
    """Index of target in a, or -1."""
    i = lower_bound(a, target)
    return i if i < len(a) and a[i] == target else -1

#include <vector>
using namespace std;

// First index i with a[i] >= target, or a.size() if there is none.
int lowerBound(const vector<int>& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid;
        }
    }
    return lo;
}

// Index of target in a, or -1.
int search(const vector<int>& a, int target) {
    int i = lowerBound(a, target);
    return (i < (int)a.size() && a[i] == target) ? i : -1;
}

class BinarySearch {
    // First index i with a[i] >= target, or a.length if there is none.
    static int lowerBound(int[] a, int target) {
        int lo = 0, hi = a.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] < target) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }

    // Index of target in a, or -1.
    static int search(int[] a, int target) {
        int i = lowerBound(a, target);
        return (i < a.length && a[i] == target) ? i : -1;
    }
}

Why it’s O(log n)

Each pass through the loop at least halves hi - lo. After k passes at most n / 2ᵏ elements remain, so the loop runs at most about log₂ n + 1 times.

Space is O(1): three integers, no recursion.

Common mistakes

lo = mid       # ✗ stuck when hi == lo + 1
lo = mid + 1   # ✓ a[mid] < target, so mid itself is ruled out

int mid = (lo + hi) / 2;        // ✗ can overflow
int mid = lo + (hi - lo) / 2;   // ✓ same value, no overflow

Variations

• Upper bound. The first index with a[i] > target: change < to <=. The number of copies of target is upper − lower, and the last copy is at upper − 1.
• Binary search on the answer. The “array” doesn’t exist; you have a check ok(x) that is false, false, …, then true, true, … Search x for the first true. Classic example: the smallest ship capacity that moves every package within D days.
• Rotated sorted array. One half around mid is always sorted. Compare with that half’s ends to decide whether the target can be there.
• Real numbers. For a continuous answer, loop a fixed number of times (say 100) instead of while lo < hi, and set lo = mid or hi = mid.
• Library versions. Python bisect.bisect_left, C++ std::lower_bound, Java Arrays.binarySearch. Java returns -(insertion point) - 1 when the value is missing, not -1.