Linear Search

The object of the linear search algorithm is to find a node in the list which has an attribute which matches a given target value.  We will use a Boolean variable searching which becomes false when a matching node is found.


accessfirst(exlist, exav)
searching = true

while searching and validaccess(exlist, exav) do
{
   if exav^.attr == target then
      searching = false
   else
      accessnext(exlist, exav)
}
if searching then
   target not present
else
   exav gives access to matching node

This algorithm works for an empty list.  It also works where the list has only one node.  We can illustrate the possible results of the search as a table:

LS Tab1

If there are N nodes in a list an unsuccessful search will always need N comparisons.  For a successful search we would expect an average of N/2 comparisons to be required.  However, if the list is ordered on the relevant attribute we can reduce the number of comparisons required for an unsuccessful search to N/2 as well.  To do this we introduce another Boolean variable, hoping, which becomes false if a value greater than the target value is encountered:


accessfirst(exlist, exav)
searching = true
hoping = true

while searching and hoping and validaccess(exlist, exav) do
{
   if exav^.attr = target then
      searching = FALSE
   else if exav^.attr > target then
      hoping = FALSE
        else
           accessnext(exlist, exav)

searching still indicates whether a match has been found, but there are now three possible outcomes for the search:

LS Tab2

Next: Adding Nodes