Easy to Describe, Easy to Get Wrong

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. Jon Bentley found most professional programmers he asked could not write it correctly, and the JDK's own version carried a midpoint overflow bug until Joshua Bloch reported it 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 number of trucks that can ship every package
// in &lt;= D days, given truck capacity. Predicate is monotonic in capacity.
public static int MinCapacity(int[] weights, int days)
{
    int low = weights.Max();        // can&apos;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

// Stop on absolute precision rather than equality
public static double Sqrt(double x, double eps = 1e-9)
{
    double low = 0, high = Math.Max(1, x);
    while (high - low > eps)
    {
        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&lt;T&gt;, 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&lt;T&gt;.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 = midchanges nothing. Always advance by at least one on the "exclude mid" branch.

4. Non-monotonic predicate. Binary search requires predicateto 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 loops forever due to rounding. Use a 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 — overflow is real even in 2026 with 64-bit indices.
  • Floating-point: use eps or fixed iteration count; never test equality.
  • Reach for Array.BinarySearch / MemoryExtensions.BinarySearch on sorted data before rolling your own.