Binary Search

Binary search works on sorted arrays by comparing the target to the middle element. If the middle element is the target, return it. If the target is less, the answer must be in the left half — discard the right. If the target is greater, discard the left. Each comparison eliminates half the remaining candidates. On an array of one million elements, at most 20 comparisons are needed.

The iterative version uses two pointers, lo and hi, that converge on the answer. The critical detail is computing mid as lo + (hi - lo) / 2 instead of (lo + hi) / 2 — the latter can overflow when lo and hi are large integers in languages with fixed-width integers. The loop continues while lo <= hi; when they cross, the element is not present.

function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

When the array has duplicates and you want the first or last occurrence, don't return immediately on a match. For the leftmost match: when arr[mid] === target, record mid and set hi = mid - 1 to keep searching left. For the rightmost match: record mid and set lo = mid + 1. This pattern also powers "find first position where condition is true" questions.

Advanced uses of binary search don't search an array at all — they search a range of possible answers. If you need the minimum speed at which all packages can be shipped within D days, define a check(speed) function and binary search over speeds. This works whenever the answer space is ordered and the feasibility check is monotonic (once it's true it stays true, or vice versa).