2.1 SEQUENTIAL SEARCH 43
2.1 Sequential Search
In search algorithms, we are concerned with the process of looking through a
list to find a particular element, called the target. Although not required, we
usually consider the list to be unsorted when doing a sequential search, because
there are other algorithms that perform better on sorted lists. Search algo-
rithms are not just interested in whether the target is in the list but are usually
part of a larger process that needs the data associated with that key. For exam-
ple, the key value might be an employee number, a serial number, or other
unique identifier. When the proper key is found, the program might change
some of the data stored for that key or might simply output the record. In any
case, the important task for a search algorithm is to identify the location of the
key. For this reason, search algorithms return the index of where the record
with the key is located. If the target value is not found, it is typical for the algo-
rithm to return an index value that is outside the range of the list of elements.
For our purposes, we will assume that the elements of the list are located in
positions 1 to N in the list. This allows us to return a value of zero if the target
is not in the list. For the sake of simplicity, we will assume that the key values
are unique for all of the elements in the list.
Sequential search looks at elements, one at a time, from the first in the list
until a match for the target is found. It should be obvious that the further
down the list a particular key value is, the longer it will take to find that key
value. This is an important fact to remember when we begin to analyze
sequential search.
The complete algorithm for sequential search is
SequentialSearch( list, target, N )
list the elements to be searched
target the value being searched for
N the number of elements in the list
for i = 1 to N do
if (target = list[i])
return i
end if
end for
return 0
