Let’s see how to write binary search in Python. The code sample here uses arrays. If you don’t know how arrays work, don’t worry; they’re covered in the next chapter. You just need to know that you can store a sequence of elements in a row of consecutive buckets called an array. The buckets are numbered starting with 0: the first bucket is at position #0, the second is #1, the third is #2, and so on.
The binary_search function takes a sorted array and an item. If the item is in the array, the function returns its position. You’ll keep track of what part of the array you have to search through. At the beginning, this is the entire array:
low = 0
high = len(list) - 1
Each time, you check the middle element:
mid = (low + high) / 2 <---- (mid is rounded down by Python automatically if (low + high) isn’t an even number.)
guess = list[mid]
If the guess is too low, you update low accordingly:
if guess < item:
low = mid + 1
And if the guess is too high, you update high. Here’s the full code:
EXERCISES
1.1 Suppose you have a sorted list of 128 names, and you’re searching through it using binary search. What’s the maximum number of steps it would take?
1.2 Suppose you double the size of the list. What’s the maximum number of steps now?
Answers (Drag below block) :
7 / 8
GrayCS 