Binary Search (Iterative)

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

Algorithm

Basic Implementation

basic.py

arr = [1, 3, 5, 7, 9, 11, 13]
target = 11
lo = 0
hi = len(arr) - 1
result = -1
while lo <= hi:
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        result = mid
        break
    if arr[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(result)

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.

Step 2 - Window narrows to the right

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

Step 3 - Second midpoint matches

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

Complexity

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

Implementation notes

Python: use floor division (//) for mid. Do not call bisect.bisect_left; it hides the loop the lesson is teaching.
The replay highlights the [lo, hi] window, mid, and which branch (left half / right half / match) the step takes.

inclusive bounds `lo` and `hi` are both inclusive; the loop runs while `lo <= hi`.

overflow-safe midpoint `mid = lo + (hi - lo) // 2` avoids `(lo + hi)` overflow on large inputs.