Searching an Array

Once you can store many values in one array, the next question is usually about the array as a whole. What is the typical value of the numbers stored there? Which one is the biggest? Neither question can be answered by looking at a single element. Each one requires visiting every position in the array and combining what you find along the way.

The two classic whole-array problems in this article are finding the average of all the elements and finding the largest element. Both are solved with a for loop, and both follow a pattern you will reuse many times: keep a small amount of running information, update it as you move through the array, and read the answer once the loop finishes.

Suppose A is an array of doubles and you want its average. The approach has two stages. First, a for loop adds up every number in the array. Second, the total is divided by the length of the array. The result is the average. Follow the first stage with a small array, A = [4, 11, 7, 2]. The loop keeps a single variable, total, that starts at 0. On each pass it adds the current element to total, so total grows from 4 to 15 to 22 to 24 as the loop visits each position.

Only total changes while the loop runs. Each element enters the calculation exactly once, and the loop never needs to look back at earlier elements. When the loop ends, total holds 24, the sum of every element in the array.

An average is computed by summing every element and dividing by the array length after the loop finishes. The loop only does the adding. The division happens once, at the end. This separation is deliberate. Dividing inside the loop would produce a wrong answer, because you would be dividing partial totals instead of the complete sum.

A second common task is to find the largest number in an array. The strategy is to walk through the array while remembering the largest value seen so far. That remembered value is stored in a variable, which this course calls max. Whenever the loop meets an element larger than the current value of max, max is updated to that larger element. The loop does not need to remember anything else.

Notice that the answer is not known in advance. It is built up one comparison at a time, and only the final state of max reveals the result. In the array above, max is replaced once, when 11 is met, and then survives the remaining comparisons unchanged.

A question remains before the loop can start: what should max contain at the beginning? Whatever you choose must be a value that the array can actually provide, or the comparison logic will not behave correctly. One reasonable choice is to start max at the first element, A[0], and then examine the remaining elements starting from A[1]. Because the first element is already in max, the loop only needs to compare against the rest of the array. This choice guarantees that max begins with a value that really is in the array.