Binary Search —

I'm thinking of a number between 1 and 1,000,000. You can guess, and I'll tell you "higher" or "lower." How many guesses do you need?

If you guess sequentially — 1, 2, 3 — you might need a million guesses. But if you always guess the middle of the remaining range... think about how fast that narrows things down.

Half. Then half again. Then half again. How many times can you halve a million before you hit 1?

That's log₂(1,000,000) ≈ 20. Twenty guesses. That's binary search.

The Template

Here's where most people go wrong: they understand the concept but write buggy code. Off-by-one errors in binary search are so common that Jon Bentley found 90% of professional programmers get it wrong.

Before I show you the correct template — try writing it yourself. Search for target in a sorted array nums. Return the index, or -1 if not found. What's your loop condition? How do you update left and right?

Here's the version that works:

function search(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

while (left <= right) {     const mid = left + Math.floor((right - left) / 2);     if (nums[mid] === target) return mid;     if (nums[mid] < target) left = mid + 1;     else right = mid - 1;   }

return -1; }

Three details, each preventing a specific bug:

1. left <= right — not <. What happens with a single-element range if you use < instead? Walk through it mentally.

1. left + Math.floor((right - left) / 2) — not (left + right) / 2. With very large indices, left + right can overflow. In JavaScript this won't crash (numbers are floats), but in Java or C++ it's a real bug. The habit matters.

1. mid + 1 and mid - 1 — you already checked mid. If you set left = mid instead of mid + 1, what happens with a two-element array where the target is the second element? Infinite loop.

Each of these details has bitten someone in a real interview. Can you explain why each one is necessary, not just that it is?

Beyond Find-the-Target

Binary search's real power isn't finding a specific value. It's this insight: any problem with a monotonic yes/no boundary can be binary searched.

What does that mean? If you can frame a problem as "find the first position where some condition becomes true" — and that condition is false for all positions before and true for all positions after — binary search applies.

Example: find the position where target should be inserted to keep the array sorted.

function searchInsert(nums: number[], target: number): number {
  let left = 0, right = nums.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) left = mid + 1;
    else right = mid;
  }
  return left;
}

Notice the differences from the first template: right = nums.length (not length - 1), left < right (not <=), right = mid (not mid - 1). This is the "leftmost boundary" variant. Different invariant, different code.

Here's the question: why does this variant use right = mid instead of right = mid - 1? What would break if you used mid - 1? Think through a concrete example before reading on.

The answer: when nums[mid] >= target, mid itself might be the insertion point. Setting right = mid - 1 would skip it. In the exact-match template, you've already checked mid and ruled it out. Here, you haven't.

The Interview Signal

When an interviewer mentions sorted input, they're handing you log(n) on a plate. Take it. When they don't mention sorted input but the answer space is monotonic — "find the minimum speed that satisfies X" — you can often sort it yourself or binary search the answer directly.

Variant	Time	Space
Iterative	O(log n)	O(1)
Recursive	O(log n)	O(log n) stack

Always go iterative. Recursive binary search spends O(log n) stack frames for zero benefit.

Reflection

Two questions. First: explain the difference between the exact-match template and the leftmost-boundary template — what invariant is each maintaining? Second: give an example of a problem that doesn't look like binary search on the surface but has a monotonic decision boundary. If you can answer both, you're not just coding binary search — you're thinking in it.

Original article: [jamesperalta.com](https://jamesperalta.com/learn/dsa/binary-search)