🔍 Binary Search

How It Works

Binary search finds a target value in a sorted array by repeatedly halving the search space. Instead of checking every element, it compares the target to the middle element and discards the irrelevant half.

Algorithm Steps

1. Initialize lo = 0, hi = n-1
2. Compute mid = Math.floor((lo + hi) / 2)
3. If arr[mid] === target: found! Return mid
4. If arr[mid] < target: target is in right half → lo = mid + 1
5. If arr[mid] > target: target is in left half → hi = mid - 1
6. Repeat until found or lo > hi

Key Code

function* binarySearchGen(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    yield { lo, hi, mid, arr };           // pause here to visualize
    if (arr[mid] === target) {
      yield { lo, hi, mid, found: true };
      return mid;
    } else if (arr[mid] < target) {
      lo = mid + 1;                        // discard left half
    } else {
      hi = mid - 1;                        // discard right half
    }
  }
  yield { notFound: true };
  return -1;
}

Why It's Fast

Each step eliminates half the remaining candidates. An array of 1,000,000 elements needs at most 20 steps (log₂ 1,000,000 ≈ 20). Compare that to linear search's worst case of 1,000,000 steps.

Complexity