Linear Search

To perform a linear search of data held in an array, the search starts at one end (usually the low numbered element of the array) and examines each element in the array until one of two conditions is met., either Condition 1: the target has been found or Condition 2: the end of the data has been reached (the target value is not in the data set).

Note that the algorithm requires that both tests are performed and that the search terminates when one of the conditions becomes true. The second test is required to prevent the algorithm from attempting to search past the end of the data. For illustration, consider the following data set. Again, element 0 is leftmost:

ADS 03 AB

To search for the value 7 in the array, we start by examining the first element of the array. This does not match the target, so we increment the index counter, and try again. We now examine the next element of the array, which has the value of 23. This does not match the target, so we again increment the counter.  This now means that we are examining the element containing 7. This is what we are looking for, so the search is terminated, and the result of the search is reported back to the calling function. It is usual to return the index of the element containing the target, but there may be circumstances where a different return value may be needed.

Consider the case where we are searching for the value 17 in the array. Again we start at index 0, and compare with the value contained at that position in the array. As the value at position 0 does not match, the index is incremented and element 1 is examined. This contains 23, which does not match. Each time that there is no match the index is incremented. At some stage in the process, the end of the array is reached, and we must arrange to stop the search. Failure to stop the search will result in the program ‘running away’ with unpredictable (and probably unwanted) results.

It is traditional to indicate that the search did not find the target by returning the value -1 to the calling function.  Remember that it is usual to return the index of the target if it is found.  Summarising, the pseudocode for the process can be outlined thus:


while ( (not found ) and (index < size of array ))
{
   if ( array[index] = target )
   {
      found = TRUE
   }
   else
   {
      index++
   }
}

/* exited loop. Either because target was found or reached end of array. The next */
/* section determines what the exit condition was and calculates the value to return */

if ( found )
{
   return index
}
else
{
   return -1
}

Linear search is simple to code, but requires on average to search half of the array each time the target is found. If the target is not in the array then every item in the array will be examined.

 Next: Binary Search