Sorting & Searching

Binary Search & Variants

The canonical O(log n) search over sorted, random-access data — and its disguises: first/last occurrence, lower/upper bound, and searching a rotated array.

Requires sorted order and O(1) random access — works on arrays and Lists backed by arrays, not linked lists
Halves the search space each step: O(log n) comparisons total
Classic bug: mid = (lo + hi) / 2 overflows for large lo/hi; use lo + (hi - lo) / 2
Lower bound (first index ≥ target) and upper bound (first index > target) are different loop invariants than exact-match search
Java's Arrays.binarySearch/Collections.binarySearch return -(insertionPoint) - 1 on a miss — a negative encoding, not a plain -1

Binary search — exact match

static int binarySearch(int[] a, int target) {
    int lo = 0, hi = a.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;      // avoids (lo + hi) overflow
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Binary search, disguised
Problem shape	What changes
First/last occurrence of a duplicate	lower bound / upper bound instead of exact match
Search in a rotated sorted array	determine which half is sorted, then decide which side to recurse into
"Smallest X such that condition(X) holds"	binary search over the answer, not the array — see Binary Search On Answer