Binary Search in C++: Iterative Algorithm, Invariant, and Complexity

Binary search finds a target in a sorted sequence by repeatedly discarding half of the remaining range. The precondition matters: applying binary search to unsorted data produces an answer that may look plausible but is not reliable.

Iterative C++ implementation

#include <vector>

int binary_search_index(const std::vector<int>& values, int target) {
    int left = 0;
    int right = static_cast<int>(values.size()) - 1;

    while (left <= right) {
        const int middle = left + (right - left) / 2;
        if (values[middle] == target) return middle;
        if (values[middle] < target) left = middle + 1;
        else right = middle - 1;
    }
    return -1;
}

Why this version is safer

left + (right - left) / 2 avoids the overflow risk of (left + right) / 2 when indexes are large. The inclusive range ends when left > right; at that point every viable index has been examined or ruled out. Returning -1 gives callers an explicit not-found result.

Correctness invariant

At the start of every iteration, if the target exists, it is inside the inclusive range [left, right]. Comparing the middle element tells us which half cannot contain the target because the input is sorted. Each update preserves the invariant while shrinking the range, so the loop terminates after O(log n) comparisons.

Common mistakes

• Searching unsorted input.
• Using left < right with an inclusive range and skipping the final candidate.
• Forgetting to move past middle, which can create an infinite loop.
• Assuming a particular duplicate index; this implementation returns any matching index.

In production C++, prefer std::binary_search for a yes/no answer or std::lower_bound when you need the insertion point.