Easy to Describe, Easy to Get Wrong

Take a typical case, made up for illustration. An audit service kept the day's order events sorted in memory and answered “show me 14:00 to 14:05” by scanning from the start. Late in the day that meant walking most of ten million events per request. The fix was obviously binary search, and the first version hung in production: with two elements left, low = mid never moved.

That is binary search in one story. The idea takes a sentence; the bugs live in the details of the loop. When Jon Bentley asked his CMU class to write one, most of the implementations were broken, and the JDK's own version, which Joshua Bloch wrote, carried a midpoint overflow bug for about nine years until it was reported to Sun; Bloch wrote it up in 2006. Below is one invariant, the half-open range [low, high), that makes every variant come out right, plus binary search on the answer.

If your binary search has ever hung
  • You write (low + high) / 2 without thinking about overflow
  • You can't remember whether the loop is while (low < high) or <=
  • You've hit an infinite loop because low = mid instead of mid + 1
  • You don't know how to find the first occurrence vs any occurrence

One Invariant for Every Variant

Pick one invariant and never deviate. The cleanest is the half-open interval [low, high):

  • low is the smallest index that might be the answer.
  • high is one past the largest index that might be the answer.
  • The search space size is high - low; we stop when it's 0.
  • Every iteration shrinks the space by at least half → O(log n) guaranteed.

flowchart LR
    S["Start: low=0, high=n"] --> C{"low &lt; high?"}
    C -->|yes| M["mid = low + (high - low) / 2"]
    M --> P{"predicate(mid)?"}
    P -->|true| L["high = mid<br/>(answer ≤ mid)"]
    P -->|false| H["low = mid + 1<br/>(answer &gt; mid)"]
    L --> C
    H --> C
    C -->|no| R["Result: low<br/>= first index where predicate is true"]

    style M fill:#0078D4,color:#fff,stroke:#005a9e
    style R fill:#16a34a,color:#fff,stroke:#15803d

Lower Bound, Ranges and Searching the Answer

Step 1: The canonical lower-bound template

// Returns the smallest index in [0, n] where predicate(i) is true.
// If never true, returns n. Predicate must be monotonic:
// false, false, ..., false, true, true, ..., true
public static int LowerBound(int n, Func<int, bool> predicate)
{
    int low = 0, high = n;
    while (low < high)
    {
        int mid = low + (high - low) / 2;     // ← overflow-safe
        if (predicate(mid)) high = mid;       // mid might be the answer
        else                low = mid + 1;    // mid is definitely not
    }
    return low;
}

Step 2: Search for an exact value (textbook)

public static int IndexOf(int[] arr, int target)
{
    int idx = LowerBound(arr.Length, i => arr[i] >= target);
    return (idx < arr.Length && arr[idx] == target) ? idx : -1;
}

Step 3: First and last occurrence in O(log n)

public static (int first, int last) Range(int[] arr, int target)
{
    int first = LowerBound(arr.Length, i => arr[i] >= target);
    int last  = LowerBound(arr.Length, i => arr[i] >  target) - 1;
    if (first == arr.Length || arr[first] != target) return (-1, -1);
    return (first, last);
}

Step 4: Binary search on the answer (optimization)

// Capacity-planning: smallest truck capacity that ships every package, in
// order, within D days (one truckload a day). Predicate is monotonic in capacity.
public static int MinCapacity(int[] weights, int days)
{
    int low = weights.Max();        // can't be smaller than heaviest pkg
    int high = weights.Sum() + 1;   // upper bound: one truck does it all

    bool Feasible(int cap)
    {
        int trucks = 1, load = 0;
        foreach (var w in weights)
        {
            if (load + w > cap) { trucks++; load = 0; }
            load += w;
        }
        return trucks <= days;
    }

    // LowerBound on a window [low, high) — same template, works perfectly
    while (low < high)
    {
        int mid = low + (high - low) / 2;
        if (Feasible(mid)) high = mid; else low = mid + 1;
    }
    return low;
}

Step 5: Floating-point binary search

// Run a fixed number of halvings rather than testing equality or an absolute eps:
// with eps = 1e-9, Sqrt(1e18) never ends, because doubles near 1e9 are ~1.2e-7 apart
public static double Sqrt(double x)
{
    double low = 0, high = Math.Max(1, x);
    for (int i = 0; i < 100; i++)
    {
        double mid = (low + high) / 2;
        if (mid * mid > x) high = mid; else low = mid;
    }
    return low;
}

Step 6: Use the BCL when you can

// .NET BCL — well-tested, supports IComparer<T>, returns bitwise complement
// of the insertion point on miss
int idx = Array.BinarySearch(arr, target);
if (idx < 0) idx = ~idx;   // would-insert-at index

// Spans (zero-allocation)
ReadOnlySpan<int> span = arr;
int idxSpan = MemoryExtensions.BinarySearch(span, target);

// SortedSet<T>.GetViewBetween / SortedDictionary for range queries
var sorted = new SortedSet<int>(arr);
var range = sorted.GetViewBetween(10, 20);

How Binary Searches Break

1. (low + high) / 2 overflow. When low and high are large positive ints, their sum overflows to negative and you index out of bounds. Always write low + (high - low) / 2.

2. Mixing < and <= with closed intervals. The closed-interval form ([low, high]) needs while (low <= high) and high = mid - 1. Mixing the half-open template with closed-interval termination causes infinite loops or off-by-ones. Pick one and never mix.

3. low = mid instead of mid + 1. Classic infinite loop: whenhigh - low == 1, mid == low; assigning low = mid changes nothing. Always advance by at least one on the "exclude mid" branch.

4. Non-monotonic predicate. Binary search requires predicate to be false-then-true (or true-then-false) across the range. If the array isn't sorted, or the optimization function isn't monotonic, you get wrong answers without a crash. Assert sortedness in debug builds.

5. Floating-point equality. while (low != high) on doubles can loop forever due to rounding, and so can an absolute tolerance smaller than the gap between neighbouring doubles. Use a relative tolerance, or run a fixed number of iterations (100 iterations halves the range by 2^100 — far below any precision you need).

6. Reinventing it. For sorted arrays, lists, or spans of comparable elements, the BCL'sArray.BinarySearch / List<T>.BinarySearch / MemoryExtensions.BinarySearch are battle-tested. Use them unless you genuinely need a custom predicate.

How I Write Them Now

  • Memorize one template: half-open [low, high), predicate-based, returns low.
  • For exact-match search, run lower bound and check arr[idx] == target.
  • For first/last occurrence, run lower bound twice with >= target and > target.
  • For optimization ("smallest X that satisfies Y"), define a monotonic Feasible(x) and reuse the same template.
  • Always write low + (high - low) / 2. Array indices in C# and Java are 32-bit ints, so the overflow is real.
  • Floating-point: use eps or fixed iteration count; never test equality.
  • Reach for Array.BinarySearch / MemoryExtensions.BinarySearch on sorted data before rolling your own.

Binary Search Beyond Sorted Arrays

Once you see binary search as a way of finding the boundary in any monotonic yes/no question, you find uses for it everywhere.

git bisect is binary search over commits. You mark one commit good and another bad, and Git halves the range until it finds the commit that broke things. With a script to test each commit, it runs by itself:

git bisect start HEAD v2.4.0
git bisect run ./scripts/check-tax-rounding.sh

A bug that appeared somewhere in 1,000 commits takes about 10 steps to pin down. I've seen teams spend days reading diffs for what git bisect finds in a handful of automated runs.

Searching the answer space is the other big one. Suppose you want the smallest batch size that meets a latency goal, or the highest load a service can take. If the answer is monotonic, you can binary search over candidate values and test each one. This is how capacity tests can find a limit in a few runs rather than dozens.

Databases use it too

A B-tree lookup is binary search spread over disk pages. Understanding that explains why range queries work, why an index on (a, b) usually can't efficiently answer a query on b alone (PostgreSQL 18's skip scan helps only when a has few distinct values), and why a sorted, append-heavy key behaves differently to a random UUID. Random keys scatter inserts across the tree, which is why time-ordered IDs such as UUIDv7 are now the better default for primary keys.

Real data isn't uniform

When values are spread evenly, interpolation search can beat binary search, though it degrades badly on skewed data, so it's rarely worth it. In practice, cache behaviour matters more. On modern CPUs, a linear scan through a small array of about a hundred items can be faster than binary search, because it avoids branch mispredictions and cache misses. Measure before you optimise a small lookup.

Be careful with duplicates and floats. Decide whether you want the first or last match, and write that into the loop's invariant. With floats, loop for a fixed number of iterations or until the range is below a tolerance, rather than testing for equality, because lo and hi may never meet.