Problem Context

Binary search is the algorithm everyone "knows" and almost no one writes correctly on the first try. Jon Bentley reported in 1986 that 90% of professional programmers couldn't implement it without bugs after several hours; forty years later, the famous(low + high) / 2 overflow bug still shipped in java.util.Arrays.binarySearchuntil Joshua Bloch flagged it in 2006. The lesson isn't that binary search is hard — it's that off-by-one errors, overflow, and unclear loop invariants compound viciously when you're halving an interval.

Modern interview and production work expects more than the textbook version. You need lower bound and upper boundvariants, "binary search on the answer" for optimization problems, and the discipline to pick a single loop invariant and stick with it. This guide is one mental model that works for all of them.

🤔 Sound familiar?
  • 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

This is one invariant — half-open [low, high) — that solves all four binary-search variants without bugs.

Concept Explanation

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

Implementation

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);

Pitfalls

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.

Practical Takeaways

  • 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.