Python Binary Search Algorithm
Search sorted lists in logarithmic O(log n) time. Run and understand binary search in Python, including step-by-step logic, edge cases, and optimizations.
How it Works
Binary search is an exceptionally efficient algorithm for finding an item in a sorted list. Unlike linear search which scans every element sequentially in O(n) time, binary search works by repeatedly dividing the search interval in half.
The search begins by examining the middle element of the array. If the target value matches the middle element, its position is returned. If the target is smaller, the algorithm narrows its search to the lower half; if the target is larger, it narrows it to the upper half. This process repeats until the element is found or the subarray size drops to zero.
To implement binary search in Python, we use two pointers (low and high) to track the active search boundaries. Since the search space decreases by half at each step, the algorithm executes in O(log n) time, making it ideal for massive databases.
Source Code
A standard iterative binary search implementation that returns the index of a target element in a sorted list.
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid
if guess > target:
high = mid - 1
else:
low = mid + 1
return -1
# Sorted test dataset
data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target_val = 23
index = binary_search(data, target_val)
print(f"Dataset: {data}")
print(f"Target: {target_val}")
if index != -1:
print(f"Target found at index: {index}")
else:
print("Target not found in dataset")Dataset: [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
Target: 23
Target found at index: 5Real-world Applications
- Query indexing and searching in database tables
- Finding threshold or boundary values in continuous mathematical ranges
- Autocomplete and search functions in text fields
Frequently Asked Questions
Does the list have to be sorted for binary search to work?
Yes, binary search strictly relies on the elements being sorted. If the list is unsorted, the comparison logic breaks, and you must sort the list first or use a linear search.
Why use iterative binary search over recursive binary search?
While recursive binary search is elegant, iterative binary search is often preferred in production. The iterative approach runs in O(1) auxiliary space, whereas recursive search takes O(log n) space due to the call stack, risking stack overflow on extremely large inputs.