Searching

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

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

The pinned run searches for 11 in [1, 3, 5, 7, 9, 11, 13]. The diagrams highlight the inclusive [lo, hi] window and each midpoint.

Step 1 - First midpoint is too small

lo = 0, hi = 6, mid = 3, and arr[3] = 7 is below target 11.

Probe 1 keeps the right half.i0i1i2i3i4i5i6135791113lomidtargethi

Step 2 - Window narrows to the right

Because 7 < 11, set lo = 4 and keep hi = 6.

After discarding indexes 0 through 3.i0i1i2i3i4i5i6135791113discarddiscarddiscarddiscardlomidhi

Step 3 - Second midpoint matches

Now mid = 5 and arr[5] = 11, so the algorithm returns index 5.

Probe 2 finds target 11 at index 5.i4i5i6return911135lomid == targethiindex

Complexity

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

Implementation notes

  • In C++, the input is a std::vector<int> initialized as {1, 3, 5, 7, 9, 11, 13} and read by index; the vector is never mutated.
  • Search bounds are scalar int values. hi starts at static_cast<int>(arr.size()) - 1, and the loop continues while lo <= hi.
  • The midpoint uses lo + (hi - lo) / 2, avoiding direct lo + hi addition while still producing an int index for arr[mid].
  • int result = -1 is the not-found sentinel. On a match, the code writes result = mid and immediately breaks instead of continuing the search.
  • The trace records lo=0, hi=6, mid=3 with arr[mid]=7, then moves lo to 4; the next midpoint is 5, where arr[mid]=11 sets result=5.
  • std::cout << result << std::endl writes 5. Visible allocation is the vector storage from the initializer list; mutation is limited to scalar search state.
midpoint `mid = lo + (hi - lo) / 2` (overflow-safe integer division).
inclusive window `hi` is inclusive. The loop runs while `lo <= hi`.