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.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);

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

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