Binary Search: Invariants, Off-By-One Bugs, and the Exact Loop That Never Fails

The invariant that makes the loop correct

Every correct binary search maintains one invariant: if the target exists, it lies within [lo, hi] — the current, shrinking candidate range. The loop continues while the range is non-empty (lo <= hi); each iteration either finds the target or discards a half in a way that preserves the invariant; and when the range empties, the target is provably absent.

The subtle requirement is on the midpoint update. If arr[mid] < target, the target — if present — must be to the right of mid, so the new range starts at mid + 1. If arr[mid] > target, it must be to the left including nothing at mid, so the range ends at mid - 1. Getting +1/-1 wrong does not crash; it silently discards the answer or loops forever.

int binary_search(const int arr[], int n, int target) {
    int lo = 0, hi = n - 1;          // candidate range [lo, hi], inclusive
    while (lo <= hi) {               // range non-empty?
        int mid = lo + (hi - lo) / 2;  // overflow-safe midpoint
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;   // discard [lo, mid]
        else                   hi = mid - 1;   // discard [mid, hi]
    }
    return -1;                        // range empty: not present
}

The three classic bugs (and how each smells)

Bug 1 — missing +1/-1: lo = mid or hi = mid with the inclusive range. With a two-element range where mid rounds to lo, the range never shrinks and the loop spins forever. Smell: infinite loop on tiny inputs; test [1, 2] searching for 2.

Bug 2 — wrong loop condition: while (lo < hi) with lo <= hi-style updates. This exits before examining the last candidate. Smell: target at an endpoint is reported missing; test [5] searching for 5.

Bug 3 — overflow midpoint: (lo + hi) / 2 can overflow when both indices are large ints. Smell: works in tests, undefined behavior on huge arrays. The fix is lo + (hi - lo) / 2, or in C++20, std::midpoint(lo, hi).

The two variants exams actually ask for

Exact-match search (above) is the warm-up. The two variants that matter in exams and interviews:

Lower bound — the first index whose value is >= target. The invariant changes to "everything left of lo is < target":

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (arr[mid] < target) lo = mid + 1;  // arr[mid] can't be the answer
    else                   hi = mid;      // arr[mid] might be the answer
}
return lo;  // first index with arr[lo] >= target

Note the asymmetric update (hi = mid, no -1) matching the half-open convention — mixing the two conventions in one loop is bug pattern #1 in disguise. In production code, std::lower_bound implements exactly this.

Search in a rotated sorted array — decide which half is sorted by comparing endpoints, then check whether the target lies in the sorted half. Same loop skeleton, one extra branch.

// lower_bound: first index with arr[index] >= target
int lower_bound_idx(const int arr[], int n, int target) {
    int lo = 0, hi = n;              // half-open [lo, hi)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] < target) lo = mid + 1;
        else                   hi = mid;
    }
    return lo;                        // may be n: all values < target
}

Why O(log n) — the counting argument

Each iteration halves the candidate range: n → n/2 → n/4 → ... → 1. The number of halvings until the range has one element is ⌈log₂ n⌉, so at most that many iterations, each O(1). For n = 1,000,000 that is ~20 comparisons; for n = 10⁹, ~30. This is also the exam favorite: "how many comparisons for n = 2²⁰?" — answer: at most 21 (20 halvings plus the final comparison).

The precondition is easy to state and easy to forget: the array must be sorted for the discard step to be valid. Running binary search on unsorted data returns garbage without any error — it is the algorithm's quietest failure mode.

Exercises with solutions

Work through each question before opening the solution below it.

int count_occ(const int arr[], int n, int target) {
    int lo = 0, hi = n;              // lower bound: first >= target
    while (lo < hi) {
        int m = lo + (hi - lo) / 2;
        if (arr[m] < target) lo = m + 1; else hi = m;
    }
    int first_ge = lo;
    hi = n;                          // upper bound: first > target
    while (lo < hi) {
        int m = lo + (hi - lo) / 2;
        if (arr[m] <= target) lo = m + 1; else hi = m;
    }
    return lo - first_ge;            // occurrences of target
}

Related pages