Back to Topics
Binary Search
Binary search eliminates half the search space with each comparison, achieving O(log n). It works on any monotonic function — not just sorted arrays. The key insight is: if you can define a predicate that is false for a prefix and true for a suffix (or vice versa), binary search finds the boundary.
Key Ideas
- Requires a sorted (or monotonic) search space
- Three templates: find exact match / find leftmost / find rightmost insertion point
- Use left + (right − left) // 2 to avoid integer overflow (important in Java/C++)
- Closing condition: left < right vs left ≤ right depends on whether the boundary index is included
- Binary search on the answer: search over the range of valid answers, not array indices
- Predicate trick: define a boolean function f(x) that is monotone — binary search finds the inflection point
Complexity
| Operation | Time | Space |
|---|---|---|
| Search in sorted array | O(log n) | O(1) |
| Search on answer space | O(log(range) × check) | O(1) |
| Rotated array search | O(log n) | O(1) |
Common Patterns
Classic Binary SearchFind exact target; return −1 if not found.
Left / Right BoundaryFind first or last position of a target using biased mid rounding.
Binary Search on AnswerThe answer is a value in a range; check feasibility at mid and shrink the range.
Predicate SearchDefine is_ok(x) — binary search for the smallest x where is_ok(x) is true.
Code Example
Find first position of target (left boundary)python
def search_left(nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
result = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
result = mid # record and keep searching left
right = mid - 1
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return result💡
If your O(n) linear scan feels unnecessary, ask: is the search space monotonic? Binary search may apply.