Source
Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree
Idea
Binary search finds a key in an array L sorted in non-decreasing order, . It is the array version of searching a binary search tree.
Steps:
- compute the midpoint of the current range
L[i..j] - if
L[k] == key, the record is found - if
key < L[k], the key can only be in the left part, so setj = k - 1 - if
key > L[k], the key can only be in the right part, so seti = k + 1 - stop with
-1wheni > j, i.e. the range is empty
Code
def binary_search(L, key):
i = 0
j = len(L) - 1
while i <= j:
k = (i + j) // 2
if key == L[k]:
return k
if key < L[k]:
j = k - 1 # search the first part
else:
i = k + 1 # search the second part
return -1
L = [-2, 3, 7, 10, 17]
print(binary_search(L, 17)) # 4
print(binary_search(L, 2)) # -1Example 1: Key Found
With L = [3, 14, 15, 17, 28, 31, 40, 51] and key : , then , then , then where L[7] == 51, so it returns 7.

Example 2: Key Not Found
Same array, key :
| Loop | Action | ||||
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 17 | , set |
| 2 | 4 | 7 | 5 | 31 | , set |
| 3 | 4 | 4 | 4 | 28 | , set |
| end | 5 | 4 | , return |
Worst-Case Complexity
Each comparison (cost ) halves the range:
The halving stops when one element is left, , so and
Sequential versus Binary
Sequential search is and binary search is . Since , a sorted list of one million elements may need one million comparisons with sequential search but only about 20 with binary search. The catch is that the array must be sorted first.