Searching

As I stated previously, searching an array means looking to see whether a particular value exists within an array and if so, at which index it’s located.

In a sense, it’s the inverse of reading. Reading means providing the computer an index and asking it to return the value contained there. Searching, on the other hand, means providing the computer a value and asking it to return the index of that value’s location.

While these two operations sound similar, there’s a world of difference between them when it comes to efficiency. Reading from an index is fast, since a computer can jump immediately to any index and discover the value contained there. Searching, though, is tedious since the computer has no way to jump to a particular value.

This is an important fact about computers: a computer has immediate access to all of its memory addresses, but it has no idea offhand what values are contained at each memory address.

Let’s take our earlier array of fruits and veggies, for example. The computer can’t immediately see the actual contents of each cell. To the computer, the array looks something like this:

To search for a fruit within the array, the computer has no choice but to inspect each cell, one at a time.

The following diagrams demonstrate the process the computer would use to search for "dates" within our array.

First, the computer checks index 0:

Since the value at index 0 is "apples", and not the "dates" we’re looking for, the computer moves on to the next index, as shown in the .

Since index 1 doesn’t contain the "dates" we’re looking for either, the computer moves on to index 2:

Once again, we’re out of luck, so the computer moves to the next cell:

Aha! We’ve found the elusive "dates" and now know that the "dates" are found at index 3. At this point, the computer doesn’t need to move on to the next cell of the array, since it already found what we’re looking for.

In this example, because the computer had to check four different cells until it found the value we were searching for, we’d say that this particular operation took a total of four steps.

In Chapter 2, , you’ll learn about another way to search an array, but this basic search operation—in which the computer checks each cell one at a time—is known as linear search.

Now, what is the maximum number of steps a computer would need to perform to conduct a linear search on an array?

If the value we’re seeking happens to be in the final cell in the array (like "elderberries"), then the computer would end up searching through every cell of the array until it finally finds the value it’s looking for. Also, if the value we’re looking for doesn’t occur in the array at all, the computer likewise would have to search every cell so that it can be sure the value doesn’t exist within the array.

So it turns out that for an array of 5 cells, the maximum number of steps linear search would take is 5. For an array of 500 cells, the maximum number of steps linear search would take is 500.

Another way of saying this is that for N cells in an array, linear search would take a maximum of N steps. In this context, N is just a variable that can be replaced by any number.

In any case, it’s clear that searching is less efficient than reading, since searching can take many steps, while reading always takes just one step, no matter the size of the array.

Next, we’ll analyze the operation of insertion.