Binary Search Explained with Python Code
Binary search finds an item in a sorted list by repeatedly cutting the search area in half. It is one of the most important algorithms to know, and it is far faster than checking items one by one.
The idea
Think of guessing a number from 1 to 100. You guess 50. If you are told "higher", you ignore everything from 1 to 50. Next you guess 75, and so on. Each guess removes half of the remaining possibilities.
Binary search does exactly this on a list. The list must already be sorted.
The steps
- Set low to the first position and high to the last position.
- Find the middle position.
- If the middle item is the target, you are done.
- If the target is bigger, search the right half (move low up).
- If the target is smaller, search the left half (move high down).
- If low passes high, the item is not in the list.
Python code
def binary_search(items, target):
low, high = 0, len(items) - 1
while low <= high:
mid = (low + high) // 2
if items[mid] == target:
return mid
elif items[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
A worked example
Search for 23 in [2, 5, 8, 12, 16, 23, 38, 56].
- low = 0, high = 7, mid = 3. The item is 12. 23 is bigger, so low becomes 4.
- low = 4, high = 7, mid = 5. The item is 23. Found at position 5.
It took 2 steps. Linear search would have needed 6.
Time complexity
Each step halves the search area, so the number of steps is about log base 2 of n. This is written O(log n). For one million items, binary search needs at most about 20 steps. Linear search could need a million.
| Items | Linear search (worst) | Binary search (worst) |
|---|---|---|
| 1,000 | 1,000 | 10 |
| 1,000,000 | 1,000,000 | 20 |
| 1,000,000,000 | 1,000,000,000 | 30 |
Common mistakes
- Using binary search on a list that is not sorted. The answer will be wrong.
- Using low < high instead of low <= high, which can miss the last item.
- Forgetting to move low or high past mid, which causes an endless loop.
Frequently asked questions
Does binary search work on a linked list?
Not well. It needs to jump straight to the middle, which an array allows in constant time but a linked list does not.
What is the space complexity of binary search?
The loop version uses O(1) extra space. A recursive version uses O(log n) for the call stack.
Does Python have binary search built in?
Yes. The bisect module in the standard library does it for sorted lists.