Loading...
Binary Search works on a sorted array: it compares the target with the middle element and discards the half that cannot contain it, halving the search space each step. That gives O(log n) time — a million elements take at most ~20 comparisons — which is why it underpins database indexes, std-lib lookups, and "search-the-answer" techniques.
Repeatedly halves a sorted range to zero in on the target.
a[7] = 45 equals the target — found at index 7.
| Best case | O(1) |
| Average case | O(log n) |
| Worst case | O(log n) |
| Space | O(1) |
Complexities are for the reference implementation shown; constant factors and cache behavior vary by language.
Idiomatic, copy-paste implementations. Pick your language:
Python
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid # found
elif arr[mid] < target:
lo = mid + 1 # search the right half
else:
hi = mid - 1 # search the left half
return -1 # not presentSearching [1, 3, 5, 7, 9, 11, 13] step by step:
The control flow of the algorithm as a diagram: