Binary Search in Python
Binary search repeatedly halves a sorted search range, making it much faster than checking every value in a large list.
What is Binary Search?
Binary search repeatedly halves a sorted search range, making it much faster than checking every value in a large list.
Find a sorted-list value with an iterative Python binary search.
When should you use it?
- Practice problem solving and data structures.
- Process data when every algorithm step must be explicit.
- Prepare for programming exercises, exams, and interviews.
Binary Search in Python visualizer
O(log n)Use Play or Step to follow each comparison and data movement.
Example code
main.py
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))Expected output
3How it works
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.