Binary Search (Iterative)

On a sorted array, narrow [lo, hi] window by halving until arr[mid] equals the target or the window is empty. Demonstrates the "discard half the search space" invariant.

Algorithm

Canonical input arr = [1, 3, 5, 7, 9, 11, 13] with target = 11 finishes in two frames: descend right to mid = 5, match.

Basic Implementation

basic.cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> arr = {1, 3, 5, 7, 9, 11, 13};
    int target = 11;
    int lo = 0;
    int hi = static_cast<int>(arr.size()) - 1;
    int result = -1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) {
            result = mid;
            break;
        }
        if (arr[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    std::cout << result << std::endl;
    return 0;
}

Complexity

Time: O(log n)
Space: O(1)

Implementation notes

C++: compute mid = lo + (hi - lo) / 2, not (lo + hi) / 2. Keeps the lesson aligned with overflow-safe practice even on small inputs.
Never use std::lower_bound / std::binary_search; the lesson is teaching the window-halving loop directly.
The replay highlights the [lo, hi] window, marks mid, and labels the branch taken (left half / right half / match).

midpoint `mid = lo + (hi - lo) / 2` (overflow-safe integer division).

inclusive window `hi` is inclusive. The loop runs while `lo <= hi`.