Binary Search
DSA · Arrays and Searching
Theory
Binary search finds a target in a sorted array by repeatedly halving the search range. It compares the target with the middle element: if smaller, it searches the left half; if larger, the right half. Because the range halves every step, it needs at most about log₂(n) comparisons, so one million items need only around 20 steps. The same idea applies to any monotonic condition, such as finding the smallest valid capacity.
Why we use it
It turns O(n) searching into O(log n), which is dramatically faster for large sorted data.
When to use it
Use it on sorted arrays, for "first/last position" problems, and for "binary search on the answer" problems where you can test whether a value works.
How it works
- Start: low = 0, high = n - 1 (array is sorted)
- Is low <= high? Yes: mid = (low + high) // 2. No: Return -1 (not found).
- arr[mid] == target? Yes: Return mid (found). No: Compare target with arr[mid].
- target < arr[mid]? Yes: high = mid - 1 (search left half). No: low = mid + 1 (search right half).
- Repeat with the smaller range
Syntax
low, high = 0, n-1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target: return mid
if arr[mid] < target: low = mid + 1
else: high = mid - 1
return -1
Time: O(log n) Space: O(1) Requires sorted dataExample
def binary_search(arr, target):
low, high = 0, len(arr) - 1
steps = 0
while low <= high:
steps += 1
mid = (low + high) // 2
if arr[mid] == target:
return mid, steps
if arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1, steps
data = list(range(0, 1000000, 3))
print("Index and steps:", binary_search(data, 299997))
print("Missing value:", binary_search(data, 10))Key points
- Data must be sorted
- Halves the range each step: O(log n)
- Watch the low <= high condition and mid updates
- Also used to search answer spaces