Binary Search
Requires sorted input. Each comparison eliminates half the remaining range, so even a million elements need only ~20 comparisons. The canonical divide-and-conquer search.
- Category
- Searching
- Time complexity
- O(log n)
- Space complexity
- O(1)
Pseudocode
lo ← 0, hi ← n−1 while lo ≤ hi mid ← (lo+hi)/2 if a[mid] = t: return mid if a[mid] < t: lo ← mid+1 else: hi ← mid−1 return not found
Reference implementation
def binary_search(a, t):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == t: return mid
if a[mid] < t: lo = mid + 1
else: hi = mid - 1
return -1