A Common-Sense Guide to Data Structures and Algorithms

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 ...