BeginnerBinary Search
Binary search: halve the search space
On sorted data, check the middle: it tells you which half the answer can't be in. 1 billion items take about 30 steps.
The idea
If the array is sorted and the middle value is too small, everything left of it is too small too, so throw that half away. Each step halves what's left, which is why it's O(log n).
Keep two indices, lo and hi, around the part that could still hold the answer, and shrink them until they meet.
Worked example
Find 9 in [-1, 0, 3, 5, 9, 12]
- lo=0, hi=5, mid=2 → 3 < 9 → lo = 3
- lo=3, hi=5, mid=4 → 9 == 9 → found at 4
In code (Python)
def binary_search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1O(log n) time, O(1) space.
How to spot it
- Sorted input and “find”, “first position”, “insert position”.
Common mistakes
- `lo = mid` instead of `mid + 1`, which can loop forever.
- Using `while lo < hi` with this template and missing the last element.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →