Binary Search

1. Binary search is a proof, not a trick

At every iteration you must be able to say:

If the answer exists, it is inside my current interval.

Inspect one middle candidate. Sorted order or a monotone predicate proves one entire side impossible. Discard it. The interval shrinks by roughly half, so an input of one billion candidates needs only about 30 checks.

2. Recognition signals

• A sorted array and an exact value, boundary, insertion point, predecessor, or successor.
• “First” or “last” item satisfying a condition.
• A rotated sorted array where one side around mid is still ordered.
• A conceptual sorted sequence, such as row-major matrix cells or timestamps stored per key.
• A huge numeric answer range with a monotone yes/no check.

The most useful question is: if candidate x works, do all candidates after it also work? If yes, you can search for the first true boundary.

3. Template A: exact lookup in [l, r]

Both ends are included. The interval becomes empty when l > r.

int l = 0, r = nums.size() - 1;
while (l <= r) {
    int mid = l + (r - l) / 2;
    if (nums[mid] == target) return mid;
    if (nums[mid] < target) l = mid + 1;
    else r = mid - 1;
}
return -1;

let l = 0, r = nums.length - 1;
while (l <= r) {
  const mid = l + Math.floor((r - l) / 2);
  if (nums[mid] === target) return mid;
  if (nums[mid] < target) l = mid + 1;
  else r = mid - 1;
}
return -1;

Use this for Binary Search and Search in Rotated Sorted Array.

4. Template B: first true boundary

Here the answer is known to be inside [l, r]. mid is kept when it might be the first feasible candidate.

while (l < r) {
    int mid = l + (r - l) / 2;
    if (works(mid)) r = mid;
    else l = mid + 1;
}
return l;

while (l < r) {
  const mid = l + Math.floor((r - l) / 2);
  if (works(mid)) r = mid;
  else l = mid + 1;
}
return l;

This is Koko Eating Bananas and the core of binary search on the answer.

5. Virtual arrays

A matrix whose rows are ordered end-to-start can be treated as one array without copying it:

row = floor(index / columns)
column = index % columns

That is Search a 2D Matrix. TimeMap uses the same exact idea on the timestamp list belonging to one key: find the rightmost time <= query.

6. Rotated arrays

Rotation destroys global sorted order but preserves a crucial fact: around any mid, at least one half is sorted.

• Finding the minimum: compare nums[mid] with nums[r] to locate the pivot.
• Finding a target: identify the sorted half, then test whether the target’s value lies inside it.

Do not compare the target before determining which half has meaningful sorted boundaries.

7. Traps

1. Mixing interval contracts: l < r with r = mid - 1, or l <= r with r = mid, often skips candidates or loops forever.
2. Returning mid after the loop. mid is only the last probe; boundary searches return l.
3. Failing to make progress. Every branch must remove at least one candidate.
4. Sorting an input that must return original indices. Sortedness must be provided or deliberately purchased with a clear tradeoff.
5. Using binary search when duplicates destroy the property used to identify the sorted half without adding a duplicate-handling rule.

8. Learning gate

On paper, search [1,3,5,7,9] for 7 and then for 4. Write l, mid, r, and the eliminated half for every iteration. Then explain why r = mid is correct for first-true search but wrong for a failed exact match.