Binary Search
You’ve probably played this guessing game when you were a child (or maybe you play it with your children now): I’m thinking of a number between 1 and 100. Keep on guessing which number I’m thinking of, and I’ll let you know whether you need to guess higher or lower.
You know intuitively how to play this game. You wouldn’t start the guessing by choosing the number 1. You’d 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 in order to keep eliminating half of the remaining numbers.
Let’s visualize this process with a similar game, except that we’re told to guess a number between 1 and 10:
This, in a nutshell, is binary search.
The major advantage of an ordered array over a standard array is that we have the option of performing a binary search rather than a linear search. Binary search is impossible with a standard array because the values can be in any order.
To see this in action, let’s say we had an ordered array containing nine elements. To the computer, it doesn’t know what value each cell contains, so we will portray the array like this:
Say that we’d like to search for the value 7 inside this ordered array. We can do so using binary search:
Step #1: We begin our search from the central cell. We can easily jump to this cell since we know the length of the array, and can just divide that number by two and jump to the appropriate memory address. We check the value at that cell:
Since 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:
Step #4: We inspect the final remaining cell. (If it’s not there, that means that there is no 7 within this ordered array.)
We’ve found the 7 successfully in four steps. While this is the same number of steps linear search would have taken in this example, we’ll demonstrate the power of binary search shortly.
Here’s an implementation of binary search in Ruby:
| | def binary_search(array, value) |
| | |
| | # First, we establish the lower and upper bounds of where the value |
| | # we're searching for can be. To start, the lower bound is the first |
| | # value in the array, while the upper bound is the last value: |
| | |
| | lower_bound = 0 |
| | upper_bound = array.length - 1 |
| | |
| | # We begin a loop in which we keep inspecting the middlemost value |
| | # between the upper and lower bounds: |
| | |
| | while lower_bound <= upper_bound do |
| | |
| | # We find the midpoint between the upper and lower bounds: |
| | # (We don't have to worry about the result being a non-integer |
| | # since in Ruby, the result of division of integers will always |
| | # be rounded down to the nearest integer.) |
| | |
| | midpoint = (upper_bound + lower_bound) / 2 |
| | |
| | # We inspect the value at the midpoint: |
| | |
| | value_at_midpoint = array[midpoint] |
| | |
| | # If the value at the midpoint is the one we're looking for, we're done. |
| | # If not, we change the lower or upper bound based on whether we need |
| | # to guess higher or lower: |
| | |
| | if value < value_at_midpoint |
| | upper_bound = midpoint - 1 |
| | elsif value > value_at_midpoint |
| | lower_bound = midpoint + 1 |
| | elsif value == value_at_midpoint |
| | return midpoint |
| | end |
| | end |
| | |
| | # If we've narrowed the bounds until they've reached each other, that |
| | # means that the value we're searching for is not contained within |
| | # this array: |
| | |
| | return nil |
| | end |