Binary Search in Python
Find any value in a sorted list of a million items in about 20 steps by halving the search range every time.
- low, middle and high indexes
- Why the list must be sorted
- The bisect module
Halve the range every step
The problem
Looking for one value in a list of a million items by checking each one can take a million comparisons. When the list is sorted, you can do far better: about 20 comparisons are enough, because each check rules out half of what is left.
Think of it like this
Binary search is how you look up a word in a paper dictionary. You open it in the middle, see whether your word comes before or after that page, and throw away the half that cannot contain it. You repeat with the remaining half until you land on the word.
low, high = 0, len(values) - 1📖 The pages you still have to searchmiddle = (low + high) // 2👆 Open in the middlelow = middle + 1➡️ The word comes later: drop the first halfhigh = middle - 1⬅️ The word comes earlier: drop the second halfBinary search finds a value in a sorted list by repeatedly comparing it with the middle element and discarding the half that cannot contain it, taking O(log n) steps.
Key points
lowandhighmark the part of the list that can still contain the target.middle = (low + high) // 2picks the middle index of that part.- If
values[middle] < target, the target is to the right, solow = middle + 1; otherwisehigh = middle - 1. while low <= high:stops when the range is empty, and the function returns-1for not found.- For 17 the search checks 12, then 25, then 17: three comparisons instead of four.
When should you use it?
- Searching large sorted data: IDs, dictionaries, sorted logs.
- Finding where to insert a value so a list stays sorted.
- Guessing games and any problem where an answer can be narrowed down by higher or lower.
When not to use it
- The data is not sorted: sorting just to search once costs more than a linear search.
- Small lists or one-off lookups:
inor a dictionary is simpler; for many lookups by key, a dict or set is even faster.
Binary Search in Python visualizer
O(log n)Use Play or Step to follow each comparison and data movement.
Example code
def binary_search(values, target):
low, high = 0, len(values) - 1
while low <= high:
middle = (low + high) // 2
if values[middle] == target:
return middle
if values[middle] < target:
low = middle + 1
else:
high = middle - 1
return -1
print(binary_search([3, 8, 12, 17, 25, 31], 17))
Result of running the code
3
Code explanation
The low and high indexes bound the remaining range. Each comparison discards the half that cannot contain the target. Time complexity is O(log n).
Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.
Practice exercises
Modify the runnable example with the exercises below to build understanding beyond copying the result.
- Try empty, single-item, and duplicate-value inputs.
- Print state after every step to observe the algorithm.
- Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Common mistakes
Using < instead of <= in the loop
With low < high, a target in the last remaining position is never checked.
while low < high:
while low <= high:
Not moving past the middle
low = middle can repeat the same middle forever.
low = middle
low = middle + 1
Finished this lesson?
Mark it as learned to track your progress.
Practice with a challenge
Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.
- Factory Production Time Find the earliest time parallel machines can finish a target number of items. Medium
- Median of Two Sorted Arrays Find the median of two sorted lists combined. Hard