4.2

Binary Search

Watch binary search divide and conquer a sorted array, eliminating half the remaining elements with each comparison. Understand why this gives O(log n) time complexity.

Prerequisite: Sorted Arrays
Target:
Array Size16
Searching for: 254
Phase: Ready
0
79
low
1
159
2
227
3
254
4
309
5
314
6
351
7
416
8
486
9
497
10
569
11
588
12
604
13
730
14
840
15
982
high
Low Pointer
Mid Pointer
High Pointer
Search Space
Eliminated
Found
1.0x
Metrics
Comparisons0
Remaining16
Search Depth0
Range[0..15]
Comparison Log
Press Play or Step to begin the search...
O(log n) Explained
Elements remaining after each step
16
n
8
n/2
4
n/4
2
n/8
1
n/16
Key Insight

Binary search eliminates half the remaining elements with each comparison. For n = 16, at most 5 comparisons are needed (log216 = 4.0).

Complexity
Best
Target is at midO(1)
Average
Halving each stepO(log n)
Worst
Search to a leafO(log n)
Space
Iterative approachO(1)