In Segment 19.7, we said that a sequential search of an array will examine on average about half of the n entries. Let’s look a little more carefully at this computation. A sequential search is either...

In Segment 19.7, we said that a sequential search of an array will examine on average about half of the n entries. Let’s look a little more carefully at this computation. A sequential search is either successful or not. Let be the probability that we will find the desired value in the array and be the probability that we will not. We further assume that the value, if found, is equally likely to be in each of the locations of the array. We need to consider each possibility. For each case, we count the comparisons and note its probability of occurrence. To find the average number of comparisons made by the search, we first multiply each probability by the number of comparisons in each case. The following table summarizes these results: