Looking up a word in a dictionary? You probably would not start at the first page and turn every page until you find it. Because the words are in order, you can open near the middle and decide which half to search next. Binary search uses that idea on a sorted list. It returns the position of a matching item, or null if the item is absent. section 1.3
Guess a number from 1 to 100
Guess 50 first. If it is too low, you can rule out 1 through 50. Guess 75 next. If that is too high, look between 50 and 75; a next guess is 63. Each answer removes about half the remaining possibilities. You need at most seven guesses, rather than up to 100 when guessing one number after another. section 1.3 section 1.4
To search an indexed, sorted list:
- Set low and high to the positions of the first and last items. section 1.4
- Check the middle item. If it matches, return its position. If it is too high, move high below the middle; if too low, move low above it. section 1.4
- Repeat while low is no greater than high. If the bounds cross without a match, return null. section 1.4
The advantage grows with the list. Simple search may check every item: its running time is O(n). Binary search repeatedly halves the possibilities, giving O(log n) running time. A list of 4 billion items could take up to 4 billion checks with simple search, but at most 32 with binary search. These rates describe how work grows, not a fixed number of seconds. section 1.5 section 1.12
def binary_search(arr, item):
low = 0 #1
high = len(arr)—1 #1
while low <= high: #2
mid = (low + high) // 2 #3
guess = arr[mid]
if guess == item: #4
return mid
elif guess > item: #5
high = mid - 1
else: #6
low = mid + 1
return None #7
my_list = [1, 3, 5, 7, 9] #8
print(binary_search(my_list, 3)) # => 1 #9
print(binary_search(my_list, -1)) # => None #10
#1 low and high keep track of which part of the list you’ll search in.
#2 While you haven’t narrowed it down to one element . . .
#3 . . . check the middle element.
#4 Found the item.
#5 The guess was too high.
#6 The guess was too low.
#7 The item doesn’t exist.
#8 Let’s test it!
#9 Remember, lists start at 0. The second slot has index 1.
#10 None means null in Python. It indicates that the item wasn’t found.
The Python implementation shows low and high tracking the remaining interval, a middle-index check on each pass, and None returned when the item is absent. section 1.4
