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.ts 
const arr: number[] = [1, 3, 5, 7, 9, 11, 13];
const target: number = 11;
let lo: number = 0;
let hi: number = arr.length - 1;
let result: number = -1;
while (lo <= hi) {
    const mid: number = 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

  • TypeScript: 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`.