Binary search

The core idea

Binary search needs exactly one property from the search space: at every point, you can tell which half the answer is in without checking it directly. On a sorted array that's obvious — but the same idea applies to any "monotonic" space, which is why binary search shows up far more often than "is this array sorted" questions alone would suggest.

The template that avoids off-by-one bugs

function binarySearch(sorted, target) {
  let lo = 0, hi = sorted.length - 1;
  while (lo <= hi) {              // note: <=, not <
    const mid = lo + Math.floor((hi - lo) / 2); // avoids overflow, same as (lo+hi)>>1 in JS
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1; // not found
}

Watch the search space halve, step by step

sorted = [1, 3, 6, 9, 12, 15, 20], target = 15:

Seven elements, but only two comparisons — log₂(7) ≈ 2.8, rounded up to 3 worst-case steps. Compare that to a linear scan, which could need all 7. At n = 1,000,000, binary search needs about 20 steps; a linear scan could need a million.

Binary search on the answer, not the array

This is the pattern that separates candidates who've memorized one template from candidates who understand the idea. Whenever a problem asks for the minimum value that satisfies a condition (or maximum), and "does value X work?" gets easier to check as X changes monotonically, you can binary search over the range of possible answers instead of the input array.

// minimum "speed" to eat all bananas within h hours — classic answer-space search
function minEatingSpeed(piles, h) {
  function hoursNeeded(speed) {
    let hours = 0;
    for (const pile of piles) hours += Math.ceil(pile / speed);
    return hours;
  }

  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (hoursNeeded(mid) <= h) hi = mid;   // mid works — answer could be smaller
    else lo = mid + 1;                     // mid too slow — need bigger speed
  }
  return lo;
}

The array here isn't even sorted — what's monotonic is the relationship between speed and hours needed: faster speed always means fewer or equal hours. That monotonic relationship is the real requirement for binary search, not "is the input array sorted."

Finding a boundary (first/last occurrence)

// leftmost index where nums[i] >= target — the building block for
   "find first occurrence" and most boundary-search variants
function lowerBound(nums, target) {
  let lo = 0, hi = nums.length; // note: hi = length, not length-1, here
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo;
}

See the range collapse

Watch the live range collapse. Ten candidates become one in four comparisons — and the count of comparisons is just how many times you can halve the array.

Recognizing it in an unseen problem

• Data is sorted, or the answer space is monotonic ("if X works, does X+1 also work?")
• The prompt says "minimum/maximum value such that…"
• A brute force would try every candidate linearly — O(n) or O(n·check)
• You can write a fast "does this candidate work?" check — that check becomes the comparison inside the binary search