Binary Search
Binary search halves the search space at every step, reaching O(log n) on sorted data or over a monotonic range.
Beyond finding a single element, it is used to find a "boundary" (the first or last element that satisfies a condition) and even for "binary search on the answer". The biggest trap is off-by-one errors at the boundaries and in the stopping condition — fix one interval convention (closed or half-open) and use it consistently.
Looking up a word in a dictionary — open to the middle, see which side the word is on, and discard the other half.
- Each step halves the search space → O(log n).
- The array must be sorted first; in exchange you get very fast lookups.
How to spot it
When you see these cues in the problem, reach for Binary Search
| Keyword in the problem | Why it points to this topic |
|---|---|
| sorted array | A prerequisite for classic binary search |
| find insert position | The lower-bound variant |
| min / max meeting a predicate | Binary search on the answer space |
| O(log n) hinted in problem | Stated complexity steers toward halving |
When to use
3 typical situations where this topic applies
The array / list is sorted and you need to find a value
You need the position of an element, or the boundary of a set satisfying a condition
The problem can be reduced to: "find the smallest / largest value that satisfies X"
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
The array is unsorted and cannot be sorted (you must keep the original indexes): use a Hash Map or a linear scan
The data is tiny (n < 100): linear search is shorter code with a smaller constant — Binary Search is overkill
The predicate is not monotonic (you cannot "move in one direction" along the answer): Binary Search does not apply
Illustration
Edit the data, then press Play to see each step.
let low=0, high=nums.length-1while (low <= high) { const mid = Math.floor((low+high)/2) if (nums[mid] === target) return mid if (nums[mid] < target) low = mid+1 else high = mid-1}return -1Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function binarySearch(nums: T[], target: T): number {
let low = 0
let high = nums.length - 1
while (low <= high) {
const mid = low + Math.floor((high - low) / 2)
if (nums[mid] === target) return mid
if (nums[mid] < target) low = mid + 1
else high = mid - 1
}
return -1
}Recap
A quick summary — reread it before your interview
Key points
Maintain [low, high] as the range still under consideration; mid = floor((low + high) / 2)
If nums[mid] === target → return mid
If nums[mid] < target → discard the left half, low = mid + 1
If nums[mid] > target → discard the right half, high = mid - 1
Loop condition: low <= high (not <)
Generalization — "binary search on the answer": find the smallest/largest value satisfying a monotonic predicate, with no pre-sorted array needed
Common mistakes
Using while (low < high) instead of low <= high → misses the one-element case
Computing mid = (low + high) / 2 can overflow an integer — write low + (high - low) / 2 to be safe
Forgetting that the array must be sorted before using binary search
Complexity
Time O(log n), Space O(1)Practice problems for this topic
Grouped by difficulty — work through them in order to build confidence