Binary Search
Find a target in a sorted array by halving the search space, and get the boundary conditions right
Problem Statement
Given a sorted array of distinct integers nums and a target, return the index of target if it exists, or -1 if it does not.
Your algorithm must run in O(log n) time.
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
Output: 4
Input: nums = [-1, 0, 3, 5, 9, 12], target = 2
Output: -1Intuition
Scanning left to right is O(n) and ignores the one fact you were given: the array is sorted. Sorted means every comparison carries far more information than "match or no match".
The key insight
Look at the middle element. Three outcomes:
nums[mid] == target→ found it.nums[mid] < target→ because the array is sorted, everything at or left ofmidis also too small. Discard the entire left half.nums[mid] > target→ everything at or right ofmidis too big. Discard the entire right half.
One comparison eliminates half the remaining candidates.
Why O(log n) is dramatic
Halving repeatedly means the number of steps is how many times you can halve n before reaching 1:
| Array size | Linear scan (worst case) | Binary search |
|---|---|---|
| 100 | 100 | 7 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
A billion-element array is resolved in about 30 comparisons.
Real-world analogy
Looking up a word in a paper dictionary. You do not start at "aardvark" — you open it near the middle, see whether your word falls before or after, and throw away half the book. Then repeat.
Watch it run
Approach
Set the boundaries
lo = 0, hi = n - 1. These are inclusive — every index in [lo, hi] is still a candidate.
Loop while lo <= hi
The <= matters: when lo == hi there is exactly one candidate left, and it still has to be checked.
Compute the midpoint safely
mid = lo + (hi - lo) // 2 rather than (lo + hi) // 2.
Compare and shrink
Equal → return mid. Too small → lo = mid + 1. Too big → hi = mid - 1.
The ± 1 is essential: mid has already been tested and must leave the search space, otherwise the loop never ends.
Solution
def search(nums: list[int], target: int) -> int:
"""Return the index of target in the sorted array nums, or -1."""
lo, hi = 0, len(nums) - 1
while lo <= hi: # <= : a single remaining element still counts
mid = lo + (hi - lo) // 2 # overflow-safe midpoint
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1 # mid is too small — exclude it
else:
hi = mid - 1 # mid is too big — exclude it
return -1The Three Bugs Everyone Writes
Binary search is famously easy to get subtly wrong. All three classic bugs are about boundaries, not about the idea.
Complexity Analysis
Time Complexity
O(log n)
Space Complexity
O(1)
- Time — the search space is
n, thenn/2,n/4, … reaching1afterlog₂ nsteps. - Space — three integers. A recursive formulation would use
O(log n)stack space instead; the iterative version is preferred.
Edge Cases
Beyond Exact Matching
Binary search's real power is finding boundaries, not just values. Whenever a predicate is false, false, …, false, true, true, …, true over a range, binary search locates the flip point in O(log n) — even when there is no array at all.
- Search Insert Position — where the target would go
- First Bad Version — binary search over version numbers, using an API instead of an array
Related Problems
- Search Insert Position — the same loop, with a different return value
- First Bad Version — binary search without an array
- H-Index — the sorted variant is solvable by binary search