• Binary Search Basics
• Common Templates and Pitfalls
• Variants: First/Last/Lower/Upper Bound
• Binary Search on the Answer
• Exponential Search
• Exercises

Binary search finds a target by repeatedly halving the search space. It requires a monotonic predicate or a sorted domain.

• Time: O(log n)
• Space: O(1) iterative, O(log n) recursive
• Invariants: maintain the range where the answer can still lie

// Inclusive l, r; find index of target or -1
function binarySearch(a, target) {
  let l = 0, r = a.length - 1;
  while (l <= r) {
    const m = l + ((r - l) >> 1);
    if (a[m] === target) return m;
    if (a[m] < target) l = m + 1;
    else r = m - 1;
  }
  return -1;
}

• Mid computation: use l + ((r - l) >> 1) to avoid overflow.
• Loop condition: choose between l < r and l <= r based on invariant.
• Always move bounds: ensure progress; avoid infinite loops when m equals a bound.

// Lower bound: first index i with a[i] >= x (returns a.length if none)
function lowerBound(a, x) {
  let l = 0, r = a.length; // half-open [l, r)
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (a[m] < x) l = m + 1; else r = m;
  }
  return l;
}

// Upper bound: first index i with a[i] > x
function upperBound(a, x) {
  let l = 0, r = a.length;
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (a[m] <= x) l = m + 1; else r = m;
  }
  return l;
}

When the answer is not directly searchable in an array, define a monotonic predicate ok(x) and binary search the smallest/largest x making it true.

// Example: minimize capacity so all packages shipped in D days (LeetCode 1011)
function shipWithinDays(weights, D) {
  let l = Math.max(...weights), r = weights.reduce((s, x) => s + x, 0);
  const ok = cap => {
    let days = 1, load = 0;
    for (const w of weights) {
      if (load + w > cap) { days++; load = 0; }
      load += w;
    }
    return days <= D;
  };
  while (l < r) {
    const m = l + ((r - l) >> 1);
    if (ok(m)) r = m; else l = m + 1;
  }
  return l;
}

When the array size is unknown or unbounded, first grow a window exponentially until it brackets the target, then binary search within that window.

function exponentialSearch(a, target) {
  if (!a.length) return -1;
  if (a[0] === target) return 0;
  let i = 1;
  while (i < a.length && a[i] <= target) i <<= 1;
  const l = i >> 1, r = Math.min(i, a.length - 1);
  // inclusive binary search on [l, r]
  let L = l, R = r;
  while (L <= R) {
    const m = L + ((R - L) >> 1);
    if (a[m] === target) return m;
    if (a[m] < target) L = m + 1; else R = m - 1;
  }
  return -1;
}

1. Implement lowerBound and upperBound for a descending array.
2. Given a predicate ok(x) that is true for all x ≥ X*, find the minimal x satisfying it.
3. Given a sorted array with duplicates, return the first and last index of a value in O(log n).