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

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.js 
const arr = [1, 3, 5, 7, 9, 11, 13];
const target = 11;
let lo = 0;
let hi = arr.length - 1;
let result = -1;
while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) {
        result = mid;
        break;
    }
    if (arr[mid] < target) {
        lo = mid + 1;
    } else {
        hi = mid - 1;
    }
}
console.log(result);

Complexity

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

Implementation notes

  • JavaScript: compute mid = lo + Math.floor((hi - lo) / 2), not Math.floor((lo + hi) / 2). Keeps the lesson aligned with overflow-safe practice even on small inputs.
  • Never use a third-party binarySearch helper; the lesson is teaching the window-halving loop.
  • The replay highlights the [lo, hi] window, marks mid, and labels the branch taken (left half / right half / match).
midpoint `mid = lo + Math.floor((hi - lo) / 2)` (overflow-safe integer division).
inclusive window `hi` is inclusive. The loop runs while `lo <= hi`.