Binary search is a fast way to find a target in a sorted list. Instead of checking every item from left to right, it checks the middle item, discards the half that cannot contain the target, and repeats. That gives binary search a time complexity of O(log n), which is much faster than linear search on large sorted data.
The important requirement is sorting. Binary search only works when the list is already ordered by the same rule used during search. Python also ships with the bisect module, which provides standard-library tools for locating insertion points in sorted lists. For general sequence behavior, the Python sequence docs explain how lists and other ordered containers behave.
Iterative binary search
The iterative version keeps two bounds: low and high. Each loop computes the middle index. If the middle value is the target, the function returns that index. If the middle value is too small, the search moves right. If it is too large, the search moves left.
def binary_search(numbers, target):
low = 0
high = len(numbers) - 1
while low <= high:
mid = (low + high) // 2
guess = numbers[mid]
if guess == target:
return mid
if guess < target:
low = mid + 1
else:
high = mid - 1
return -1
values = [2, 5, 9, 12, 18, 24, 31, 40]
print(binary_search(values, 18))
print(binary_search(values, 7))
Returning -1 is a common convention when the target is absent. Another option is returning None, especially when -1 could be confused with a valid Python negative index.
Trace the search steps
Tracing the bounds makes the algorithm easier to debug. The helper below records the current low, mid, high, and middle value at each step.
def binary_search_trace(numbers, target):
low = 0
high = len(numbers) - 1
steps = []
while low <= high:
mid = (low + high) // 2
guess = numbers[mid]
steps.append((low, mid, high, guess))
if guess == target:
return steps
if guess < target:
low = mid + 1
else:
high = mid - 1
return steps
values = [2, 5, 9, 12, 18, 24, 31, 40]
print(binary_search_trace(values, 24))
This trace is also useful when teaching binary search because it shows the list shrinking after every comparison. If you need a refresher on visiting list items, the iterate through a list in Python guide covers the basic loop patterns.
Recursive binary search
The recursive version uses the same idea, but each call searches a smaller range. The base case is the point where low becomes greater than high, which means the target is not present.
def binary_search_recursive(numbers, target, low=0, high=None):
if high is None:
high = len(numbers) - 1
if low > high:
return -1
mid = (low + high) // 2
guess = numbers[mid]
if guess == target:
return mid
if guess < target:
return binary_search_recursive(numbers, target, mid + 1, high)
return binary_search_recursive(numbers, target, low, mid - 1)
values = [2, 5, 9, 12, 18, 24, 31, 40]
print(binary_search_recursive(values, 31))
The iterative version is usually the practical choice in Python because it avoids recursion-depth concerns and is straightforward to read. The recursive form is still useful for learning divide-and-conquer thinking.
Use bisect_left for sorted lists
The bisect_left() function returns the insertion point that keeps a list sorted. To use it as a search helper, check whether the returned index is still inside the list and whether the value at that index equals the target.
from bisect import bisect_left
def find_with_bisect(numbers, target):
index = bisect_left(numbers, target)
if index != len(numbers) and numbers[index] == target:
return index
return -1
values = [2, 5, 9, 12, 18, 24, 31, 40]
print(find_with_bisect(values, 12))
print(find_with_bisect(values, 13))
This is often the best choice in production code because the standard-library function is tested and concise. If your data must be sorted first, see the sort a list of tuples guide for sorting patterns beyond plain numbers.
Find an insertion point
Sometimes the goal is not only to find an item, but also to know where it should be inserted. The same bisect_left() result gives that position. insort() can insert the value while keeping the list ordered.
from bisect import bisect_left, insort
scores = [10, 20, 30, 40]
new_score = 25
position = bisect_left(scores, new_score)
print(position)
insort(scores, new_score)
print(scores)
Insertion is still a list operation, so adding near the front may require moving later items. Binary search finds the position quickly, but it does not make list insertion itself constant time.
Search records by a sorted key
For records, keep the search key sorted. The example below searches employee IDs and then uses the found index to read the matching record.
def binary_search(numbers, target):
low = 0
high = len(numbers) - 1
while low <= high:
mid = (low + high) // 2
if numbers[mid] == target:
return mid
if numbers[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
records = [(101, "Ana"), (205, "Ben"), (309, "Mia")]
ids = [record[0] for record in records]
index = binary_search(ids, 205)
if index != -1:
print(records[index])
For many lookups by ID, a dictionary is usually better because key lookup is direct. Binary search fits sorted lists when order matters, when the data is already sorted, or when you need both search and insertion positions. For text-specific searches, the find a string in a Python list guide gives additional examples.
Common mistakes
The most common binary search bug is an off-by-one error. Update low to mid + 1 and high to mid - 1; otherwise the same middle index can repeat forever. Another frequent mistake is searching unsorted data. If the list order changes, sort it again or use a different data structure.
A compact test set should cover the first item, last item, middle item, a missing item below the range, a missing item above the range, and an empty list. Those cases catch most bound mistakes before the function is used inside a larger program.
Use binary search when the data is sorted, comparisons are cheap, and repeated searching makes the upfront sorting cost worthwhile. Use a plain loop for tiny lists or one-off searches where readability matters more than asymptotic speed. Use bisect when you need standard-library reliability and insertion-point behavior. When the goal is maintaining a sorted Python list rather than only finding a match, Python bisect: Search and Insert Sorted Lists provides insertion points and insort helpers.