BINARY SEARCH
HALVE THE LIST · FIND IT FAST
prostudypk.com
Find 37 in a Sorted List
BINARY SEARCH
3
8
12
17
21
25
29
33
37
42
46
51
58
63
70
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
▲ low
▲ mid
▲ high
LINEAR SEARCH
3
8
12
17
21
25
29
33
37
42
46
51
58
63
70
binary steps
linear steps
found at index
1. Algorithm
mid = (low + high) // 2
if a[mid] == key: found
elif a[mid] < key: low = mid + 1
else: high = mid − 1
2. How Fast?
Items
Linear (worst)
Binary (worst)
15
15
4
1,000
1,000
10
1,000,000
1,000,000
20
3. Remember
Binary search works only on a sorted list
The list is halved at every step
MATRIC COMPUTER · ALGORITHMS · PUNJAB BOARDS
‹ Labs
↺
❚❚
1×
Next ›