Searching an Ordered Array
In the previous chapter, we described the process for searching for a particular value within a regular array: we check each cell one at a time—from left to right—until we find the value we’re looking for. We noted that this process is referred to as linear search.
Let’s see how linear search differs between a regular and ordered array.
Say that we have a regular array of [17, 3, 75, 202, 80]. If we were to search for the value 22—which happens to be nonexistent in our example—we would need to search each and every element because the 22 could potentially be anywhere in the array. The only time we could stop our search before we reach the array’s end is if we happen to find the value we’re looking for before we reach the end.
With an ordered array, however, we can stop a search early even if the value isn’t contained within the array. Let’s say we’re searching for a 22 within an ordered array of [3, 17, 75, 80, 202]. We can stop the search as soon as we reach the 75, since it’s impossible that the 22 is anywhere to the right of it.
Here’s a Ruby implementation of linear search on an ordered array:
| | def linear_search(array, value) |
| | |
| | # We iterate through every element in the array: |
| | array.each do |element| |
| | |
| | # If we find the value we're looking for, we return it: |
| | if element == value |
| | return value |
| | |
| | |
| | |
| | # If we reach an element that is greater than the value |
| | # we're looking for, we can exit the loop early: |
| | elsif element > value |
| | break |
| | end |
| | end |
| | |
| | # We return nil if we do not find the value within the array: |
| | return nil |
| | end |
In this light, linear search will take fewer steps in an ordered array vs. a standard array in most situations. That being said, if we’re searching for a value that happens to be the final value or greater than the final value, we will still end up searching each and every cell.
At first glance, then, standard arrays and ordered arrays don’t have tremendous differences in efficiency.
But that is because we have not yet unlocked the power of algorithms. And that is about to change.
We’ve been assuming until now that the only way to search for a value within an ordered array is linear search. The truth, however, is that linear search is only one possible algorithm—that is, it is one particular process for going about searching for a value. It is the process of searching each and every cell until we find the desired value. But it is not the only algorithm we can use to search for a value.
The big advantage of an ordered array over a regular array is that an ordered array allows for an alternative searching algorithm. This algorithm is known as binary search, and it is a much, much faster algorithm than linear search.