Binary search interview questions — variants, patterns, and recognition

The three binary-search variants you must know

Classic binary search is one of three variants. The harder two come up far more often in FAANG mediums than the classic.

The canonical binary search template

Off-by-one errors are the leading cause of binary-search bugs in interviews. This template avoids most of them:

left, right = 0, n - 1

while left <= right:
  mid = (left + right) // 2
  if arr[mid] == target:
    return mid
  elif arr[mid] < target:
    left = mid + 1
  else:
    right = mid - 1

return -1

Key boundary choices: closed interval [left, right], condition left <= right, updates mid + 1 and mid - 1. Consistent with these three, every classic binary search is mechanical.

• For boundary search, modify the equal case: when arr[mid] == target, don’t return — record the index and continue searching left (for first occurrence) or right (for last).
• For search-on-answer-space, replace the array index with a value range: left = min_possible_answer, right = max_possible_answer. The predicate replaces the array comparison.
• Mid-point overflow. For very large left + right, use mid = left + (right - left) // 2 to avoid integer overflow. Rarely matters in Python, often matters in Java/C++.

Full deep-dive with worked examples: Binary search — variants and templates.

Recognizing ‘binary search on the answer space’

This is the hardest binary search variant to recognize. Three cues:

• “Minimize the maximum” or “maximize the minimum”. Classic answer-space binary search.
• “Smallest/largest X such that…”. If you can check ‘does X work?’ for a given X, you can binary-search over X.
• Capacity / allocation problems. “What’s the smallest capacity to ship all packages in D days?” You can verify a guess; therefore binary-search the guess.
• Monotonic predicate. Formally: if isFeasible(x) is True, then isFeasible(x+1) is also True. That monotonicity is the unlock.

The 8 most common binary search interview questions

1. Binary search (classic) — Warm-up, almost always asked first
2. First and last position in sorted array — Boundary search
3. Search in rotated sorted array (I and II) — Boundary search variant
4. Find peak element — Search on answer space with implicit predicate
5. Sqrt(x) — Search on answer space
6. Capacity to ship packages within D days — Allocation, search on answer space
7. Split array largest sum — “Minimize the maximum”
8. Median of two sorted arrays — Binary search on partition (hard)

Frequently asked questions

Explore related tools