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
}

Which C++ standard does this page assume?

Standard C++17. C++ began as C with Classes in 1979 and first shipped commercially in 1985; what a compiler flag actually selects today is one of the ISO revisions below, and the committee has published a new one every 3 years since 2011. Build these listings with -std=c++17 and they compile as written.

Common questions

Where can I check this against the language itself?

Nothing on this page outranks the standard or the library reference. When this page and one of these disagree, they are right and we want to know.

• cppreference — the C++ standard library referenceThe fastest correct answer for what a container or algorithm actually guarantees.
• isocpp.org — the Standard C++ FoundationThe FAQ and the core guidelines, written by the people who define the language.
• ISO/IEC JTC1/SC22/WG21 — the C++ standards committeeWorking drafts of the standard itself, free to read, when the wording is the question.
• GCC online documentationWhat -Wall, -Wextra and the sanitizers used on these listings actually check.
• Microsoft Learn — C++ language documentationThe MSVC view, for readers whose lab machines build with Visual Studio.

Related pages