Visualizer › Searching
Binary Search
On a sorted array, compares the target with the middle element and throws away the half that cannot contain it — halving the search space every step.
How it works
- Needs sorted data.
- 1,000,000 elements need at most 20 steps.
- The same idea solves "binary search on the answer" problems (minimum possible maximum, smallest X such that…).
Complexity
- Best time: O(1)
- Average time: O(log n)
- Worst time: O(log n)
- Extra space: O(1)
Code (Python)
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
if a[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Practise: Binary Search problems