This assumes that the target item is in the list. If the algorithm were implemented on a computer that could process one comparison in 1/1,000 of a second, 5 seconds would be required, on average, for the search operation to complete. So, given a list of 10,000 items, on average 5,000 comparisons are required to find an item that is in the list. Thus, on average, successful sequential searches of an N item list require ½ N comparisons. This should not be surprising, since the “good” cases, where the target is at the front of the list, and the “bad” cases, where the target is at the end of the list, tend to cancel each other out over multiple searches. If you performed lots of searches, and determined the “mean” or “average” number of comparisons required to find a target item that you know to be in the list, you would find that, on average, you had to scan about half the list. At other times, the target item will be the very last item in the list, and every item must be examined – so for a 10,000 item list, all 10,000 items would be examined. Sometimes the target item will be right at the beginning of the list, so only one comparison is needed to find it. Now, what if the item is in the list? How many comparisons would be required to find the item? Well, as the above example with eight items showed, it varies.

In that case, an unsuccessful search of 10,000 items would require 10 seconds. Let’s say we were executing sequential search on an antique computer that requires 1/1,000 of a second to perform a comparison. So, for N = 8 items, a search that ends in failure will require N, or 8, comparisons. To begin with, if the target item is not in the list, it will be necessary to look through the entire list to verify this fact.

2.2 Let the current item be the next item in the listįigure 5.5: Sequential search for the value 20.If the current item is the same as the target item then Repeat the following steps until (a) you have reached the end of the list Let the current list item be the first item in the list. In other words, the question we would like answered is “What is the behavior of this algorithm, in general, given an arbitrary target and list of N items?” Such a description would allow us to predict the average number of comparisons required to find an arbitrary key given only the size of the list instead of the actual values. A general description of the algorithm’s efficiency, in terms of the number of items to be searched, would be much more useful. In the previous paragraph, we looked at the behavior of sequential search on a specific list of eight numbers given several different target values. Given the same list and a target value of 90, the algorithm would be forced to examine all eight items to determine that this target does not occur anywhere in the list. If, on the other hand, the target value was 50 and the list remained unchanged, this algorithm would have to examine only one item – the first item in the list. This is because the target value occurs in the sixth position of the list. When looking for the value 20, only the first six items of this particular list need to be examined. Note that step three of the algorithm is reached only in the event that the entire list was searched and the target item not discovered.įigure 5.5 illustrates the behavior of the sequential search algorithm given the eight item list (50,10,30,80,70,20,60,40) and a target value of 20. The algorithm for sequential search is expressed more formally in Figure 5.4. If you reach the end of the list without having found the item, you should print “No, did not find it” and then quit. As soon as you find the item, print “Yes, found it” and then quit. Sequential search works in the following way: starting at the first item in the list, compare each item in the list to the item you are looking for.