Returning Values from Methods

Suppose you have an array of integers and you need to know whether a particular value appears in it, and if so, where. The array gives you no hints about where the value might be. It is not sorted, and nothing else tells you which position to try first. What is the most direct method you could use?

The most direct method is also the most obvious one: look at each item in the array in turn, and check whether that item is the one you are looking for. If you find it, the search is finished. If you look at every item without finding the one you want, you can be sure the item is not in the array. This method is called a linear search. In this article you will start from code that performs the search, predict its result before running it, and then trace the mechanism that produces that result.

The following Java method searches an array of ints for a specified integer. It takes the array A and the integer N to look for. Read it once for its overall shape before you worry about individual lines. Notice that the declared return type is int, so the method hands back a single integer to whoever calls it.

Two return statements appear in this method, and they play different roles. The one inside the if block is reached only when a match has been found. The one after the loop is reached only when every position has been checked and none matched. Which of these two statements the method executes determines what the caller receives, so the rest of this article follows that choice.

Before you move on, make a prediction. Consider the array {4, 8, 8, 2} and a call to find with N equal to 8. The value 8 appears twice, at positions 1 and 2. Decide which index you expect find to return, and state the reason from the loop itself rather than from guessing.

The loop variable index is the only thing that moves through the array. It begins at 0 and increases by one each time the loop body finishes, stopping once index reaches the length of the array. On each pass the method asks a single question: does the element at this position equal N? If the answer is no, nothing is recorded and the loop moves on. If the answer is yes, the method leaves immediately and reports the position.

The diagram shows that the loop never looks ahead. The value at index 2 is an 8 as well, but the method never gets there. This is the first consequence of the design: the search stops at the first position that satisfies the comparison.

The method has no memory of earlier mismatches. It does not count them or keep a list of places it has checked. Each position is judged alone, and the answer is determined by the first position that satisfies the comparison. Because of this, when several positions hold the same value, the index returned is always the smallest of them.

In the diagram, position 1 is highlighted because it is the one the search returns. Position 2 also holds an 8, yet it is never the result. If you changed the array to {4, 8, 8, 2} and asked for the 8 again, you would still get 1, not 2, because index 1 is the smallest position holding that value.

The method can finish in exactly two ways. One is through a match, which returns an index. The other is through exhausting the array, which returns -1. The flowchart below shows the same decisions as the method, in the order control moves between them.

The branch that returns an index is taken as soon as a match appears, so it can exit the loop while many positions remain unchecked. The branch that returns -1 can only be reached after the loop condition fails, which means every position has been examined without success. This asymmetry is what lets the method conclude absence safely: it cannot claim the value is missing until it has looked everywhere.

A caller receives a single int, and that int must carry two different meanings: either the position where the value was found, or a signal that it was not found. The method relies on -1 for the second meaning. This choice is safe because -1 is never a valid index, so no real position can be confused with the not-found signal.