Binary Search
You’ve probably played this guessing game as a child: I’m thinking of a number between 1 and 100. Keep guessing which number I’m thinking of, and I’ll let you know whether you need to guess higher or lower.
You may know intuitively how to play this game. You wouldn’t begin by guessing number 1. Instead, you’d probably start with 50, which is smack in the middle. Why? Because by selecting 50, no matter whether I tell you to guess higher or lower, you’ve automatically eliminated half the possible numbers!
If you guess 50 and I tell you to guess higher, you’d then pick 75, to eliminate half of the remaining numbers. If after guessing 75, I told you to guess lower, you’d pick 62 or 63. You’d keep on choosing the halfway mark to keep eliminating half of the remaining numbers.
Let’s visualize this process where we’re told to guess a number between 1 and 10, as shown in the .
This, in a nutshell, is binary search.
Let’s see how binary search is applied to an ordered array. Say we have an ordered array containing nine elements. The computer doesn’t know offhand what value each cell contains, so we’ll portray the array like this:
Say we’d like to search for the value 7 inside this ordered array. Here’s how binary search would work:
Step 1: We begin our search from the central cell. We can immediately jump to this cell, since we can calculate its index by taking the array’s length and dividing it by 2. We check the value at this cell:
Because the value uncovered is a 9, we can conclude that the 7 is somewhere to its left. We’ve just successfully eliminated half of the array’s cells—that is, all the cells to the right of the 9 (and the 9 itself):
Step 2: Among the cells to the left of the 9, we inspect the middlemost value. There are two middlemost values, so we arbitrarily choose the left one:
It’s a 4, so the 7 must be somewhere to its right. We can eliminate the 4 and the cell to its left:
Step 3: There are two more cells where the 7 can be. We arbitrarily choose the left one, as shown in the .
Step 4: We inspect the final remaining cell. (If it’s not there, that means there is no 7 within this ordered array.)
We found the 7 in four steps. In this example this is the same number of steps linear search would have taken, but we’ll take a look shortly at another example to see the power of binary search.
Note that binary search is only possible within an ordered array. With a classic array, values can be in any order and we’d never know whether to look to the left or right of any given value. This is one of the advantages of ordered arrays: we have the option of binary search.
Code Implementation: Binary Search
Here’s an implementation of binary search in Python:
| | def binary_search(array, search_value): |
| | |
| | lower_bound = 0 |
| | upper_bound = len(array) - 1 |
| | |
| | while lower_bound <= upper_bound: |
| | |
| | midpoint = (upper_bound + lower_bound) // 2 |
| | value_at_midpoint = array[midpoint] |
| | |
| | if search_value == value_at_midpoint: |
| | return midpoint |
| | elif search_value < value_at_midpoint: |
| | upper_bound = midpoint - 1 |
| | elif search_value > value_at_midpoint: |
| | lower_bound = midpoint + 1 |
| | |
| | return None |
Let’s break this down. As with the linear_search method, binary_search accepts the array and the search_value as arguments.
Here’s an example of how to call this method:
| | print(binary_search([3, 17, 75, 80, 202], 22)) |
The method first establishes the range of indexes in which the search_value might be found. We do this with the following code:
| | lower_bound = 0 |
| | upper_bound = len(array) - 1 |
Because when starting our search, the search_value might be found anywhere within the entire array, we establish the lower_bound as the first index and the upper_bound as the last index.
The essence of the search takes place within the while loop:
| | while lower_bound <= upper_bound: |
This loop runs while we still have a range of elements in which the search_value may lie. As we’ll see shortly, our algorithm will keep narrowing this range as we go. The clause lower_bound <= upper_bound will no longer hold true once there’s no more range left, and we can conclude that the search_value is not present in the array.
Within the loop, our code inspects the value at the midpoint of the range. The following code accomplishes this:
| | midpoint = (upper_bound + lower_bound) // 2 |
| | value_at_midpoint = array[midpoint] |
The value_at_midpoint is the item found at the center of the range.
Now, if the value_at_midpoint is the search_value we’re looking for, we’ve struck gold and can return the index in which the search_value is found:
| | if search_value == value_at_midpoint: |
| | return midpoint |
If the search_value is less than the value_at_midpoint, it means the search_value must be found somewhere earlier in the array. We can then narrow the range of our search by making the upper_bound the index to the left of the midpoint, since the search_value cannot possibly be found anywhere further than that:
| | elif search_value < value_at_midpoint: |
| | upper_bound = midpoint - 1 |
Conversely, if the search_value is greater than the value_at_midpoint, it means the search_value can only be found somewhere to the right of the midpoint, so we raise the lower_bound appropriately:
| | elif search_value > value_at_midpoint: |
| | lower_bound = midpoint + 1 |
We return None once the range has been narrowed down to 0 elements, and we know with certainty that the search_value doesn’t exist within the array.
