Python Program for Binary Search
Intermediate Searching and sorting Time O(log n) Space O(1)
Finds a value in a sorted list by checking the middle item and halving the part still to search at every step.
Binary search finds an item in a sorted list. Instead of checking every item from the start, as a linear search does, it looks at the middle item and throws away the half that can't hold the target. A list of a million items takes at most 20 checks.
Program
def binary_search(items, target):
"""The index of target in the sorted list items, or -1."""
low, high = 0, len(items) - 1
while low <= high:
middle = (low + high) // 2
if items[middle] == target:
return middle
if items[middle] < target:
low = middle + 1 # target is in the right half
else:
high = middle - 1 # target is in the left half
return -1
numbers = [3, 8, 12, 17, 23, 31, 42, 56, 64, 79]
print("Index of 23:", binary_search(numbers, 23))
print("Index of 50:", binary_search(numbers, 50))
Open in the editor Download binary_search.py
Output
Index of 23: 4
Index of 50: -1
How it works
Step through the program line by line: each step below shows up as its line runs.
-
lowandhighmark the part of the list still to search. At first that's the whole list: index 0 to the last. - While anything is left to search (
low <= high),middleis the index halfway between them. - If the middle item is the target, the search is over: the function returns its index.
- Otherwise it throws away the half that can't hold the target. If the middle item is
smaller, the target can only be to its right, so
lowmoves to just past the middle. If it's bigger,highmoves to just before it. - When
lowpasseshigh, nothing is left to search: the target isn't in the list, so the function returns -1. - The program searches a sorted list for 23, which is in it, and 50, which isn't.
Searching for 23:
| Step | low | high | middle | items[middle] | Then |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 23 | Found it: return 4 |
And for 50:
| Step | low | high | middle | items[middle] | Then |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 23 | 23 < 50, so low = 5 |
| 2 | 5 | 9 | 7 | 56 | 56 > 50, so high = 6 |
| 3 | 5 | 6 | 5 | 31 | 31 < 50, so low = 6 |
| 4 | 6 | 6 | 6 | 42 | 42 < 50, so low = 7 |
| 5 | 7 | 6 | low > high: return -1 |
Time and space complexity
| Time | O(log n) |
|---|---|
| Extra space | O(1) |
Every step halves the part still to search, so a list of n items needs about log₂ n steps: 10 items take at most 4, a million at most 20. The search keeps only three numbers whatever the size of the list, so its extra space is O(1). The list must already be sorted; sorting it first costs O(n log n).
Other ways to write it
With recursion
Each call searches one half, until the half is empty (recursion). It needs O(log n) space for the calls.
def binary_search(items, target, low=0, high=None):
if high is None:
high = len(items) - 1
if low > high:
return -1
middle = (low + high) // 2
if items[middle] == target:
return middle
if items[middle] < target:
return binary_search(items, target, middle + 1, high)
return binary_search(items, target, low, middle - 1)
print(binary_search([3, 8, 12, 17, 23, 31], 17))With the bisect module
Python's standard library has binary search built in. bisect_left returns where the target is, or where it would
go to keep the list sorted.
from bisect import bisect_left
def binary_search(items, target):
index = bisect_left(items, target)
if index < len(items) and items[index] == target:
return index
return -1
print(binary_search([3, 8, 12, 17, 23, 31], 23), binary_search([3, 8, 12, 17, 23, 31], 20))Try it yourself
- Search for the first and last items (3 and 79), and for numbers outside the list, such as 1 and 100.
- Count how many times the
whileloop runs for each target, and print it next to the result. - Search a sorted list of names, such as
["Asha", "Ben", "Chen", "Dev"]: the same function works for text. - Change the function to return where the target should be inserted when it isn't found.