Binary Search Explained

Binary search is four lines and almost everyone gets it wrong the first time. The logic is easy; the boundaries are where it breaks.

The idea

Look at the middle. If it is the target, done. If the target is larger, everything to the left is irrelevant - discard half the array. Repeat.

Ten million sorted items takes about 24 steps. That is what O(log n) buys you.

function binarySearch(sorted, target) {
  let low = 0
  let high = sorted.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)

    if (sorted[mid] === target) return mid
    if (sorted[mid] < target) low = mid + 1
    else high = mid - 1
  }

  return -1
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7))   // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11], 4))   // -1

The three things that go wrong

• low < high instead of <= - misses the target when the range narrows to one element.
• low = mid instead of mid + 1 - the range stops shrinking and the loop never ends.
• Forgetting the input must be sorted - it returns a confident wrong answer rather than failing.

That last one is the dangerous one. Binary search on unsorted data does not throw; it just lies.

Finding the boundary, not the value

More useful in practice: where would this value go? That is the version behind autocomplete ranges and time-series lookups.

function lowerBound(sorted, target) {
  let low = 0
  let high = sorted.length   // note: length, not length - 1

  while (low < high) {       // note: <, not <=
    const mid = Math.floor((low + high) / 2)

    if (sorted[mid] < target) low = mid + 1
    else high = mid
  }

  return low   // insertion point
}

console.log(lowerBound([1, 3, 5, 7], 5))  // 2
console.log(lowerBound([1, 3, 5, 7], 4))  // 2 — where 4 would go

The boundaries differ from the plain search on purpose - high starts past the end and the loop uses <. Mixing the two styles is how most binary search bugs happen. Pick one per problem and keep it consistent.

Is sorting first worth it?

Sorting costs O(n log n). One binary search costs O(log n), a linear scan costs O(n). So sorting to search once is a loss.

• Searching once - just scan. O(n) beats O(n log n).
• Searching many times - sort once, then every search is O(log n).
• Exact matches only, unsorted - a Set beats both at O(1).

Binary search earns its place when you need ranges or nearest, which a hash map cannot answer at all.

Searching an answer, not an array

The advanced use: when the answer is a number in a range and you can test whether a candidate works, binary search the answer itself. "Smallest capacity that ships everything in D days" is this pattern, and it is not obvious until you have seen it once.