Animations
Binary Search — Visual Walkthrough
Watch how binary search eliminates half the search space with every single comparison.
Binary Search
Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] — Target: 13
Instead of checking every element, binary search always looks at the middle — and eliminates half the array in one comparison.
Binary Searchsorted · O(log n)
target13
1
[0]3
[1]5
[2]7
[3]9
[4]11
[5]13
[6]15
[7]17
[8]19
[9]search space
mid element
eliminated
found
left—
mid—
right—
remaining10
binary_search.py
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid # found!
elif arr[mid] < target:
left = mid + 1 # search right half
else:
right = mid - 1 # search left half
Call binary_search(arr, target=13)
step 0/17
0%
How it works
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1Binary search only works on sorted arrays. If the array is unsorted, the assumption that eliminates half the array is wrong — and the search will miss elements.
Complexity
| Approach | Time | Space |
|---|---|---|
| Linear search | O(n) | O(1) |
| Binary search | O(log n) | O(1) |
For 1,000,000 elements — linear search takes up to 1,000,000 steps. Binary search takes at most 20.