The Linear Search Algorithm

Linear Search: Basic Idea

The idea of this search is simply to look at each value in succession to see if it is the one you are looking for, until you find what you are looking for, or until you have no more values to look at.

Linear Search: Name, Input and Output

Name: SearchLinear

Input:

• sequence, a sequence of values which all have the same data type
• targetValue, a value of the same data type as the values in sequence, and whose location in sequence is being sought
• firstPosition and lastPosition, two positions in sequence which determine the range of values within sequence that will be searched, and which satisfy firstPosition <= lastPosition

Output:

• sequence, unchanged
• targetFound, a boolean quantity indicating whether the target value has, in fact, been found
• targetPosition, a position value which is the first position in sequence where the target value has been located, provided targetFound is true (Note that targetPosition is undefined if targetFound is false.)

Linear Search: Pseudocode

Algorithm SearchLinear(sequence, targetValue, firstPosition, lastPosition,
                       targetPosition, targetFound)
--------------------------------------------------------------------------
Make sequence value at first position of search range the current value
while position of current value remains valid and current value not target value
    Make value at next position the current value
endwhile
if position of current value is still valid, target value is at that position

This particular version of the algorithm assumes nothing at all about the data. It can be improved somewhat for particular sequence instances if the data is known to be sorted, but this will not affect (improve) the overall performance of the algorithm. Note that the algorithm finds the first value that's equal to the one you're looking for and is located within the search range. There may be additional instances of the target value in that range, which can be found by applying the same algorithm to an appropriately adjusted search range.

Linear Search: Performance

We say that the linear search algorithm is, in general, a O(n) algorithm, or that it has "linear time complexity".

• However, the best-case performance of linear search is O(1). This is another way of saying that if the target value is always in the first position, it doesn't matter how many data values there are, since the search time will always be constant.
• Also, the worst-case performance of linear search is O(n). This is another way of saying that if the target value is always in the last position, the search time will always be proportional to the number of data values.
• To see that the average-case performance of linear search is O(n), we may proceed as follows. The number of comparisons performed is the quantity of interest, since that is what determines that amount of work done by the linear search algorithm. First, note that if we have n data values and we search for a target value in the sequence formed by these n values, we have the following table showing how many comparisons are needed to find the target value in any given position:

  target value in position .................... 1  2  3 ... n
  number of comparisons required to find it ... 1  2  3 ... n
  

  From this is follows that the average number of comparisons is thus

  1 + 2 + 3 + ... + n   n(n+1)/2
  ------------------- = -------- = (n+1)/2 or n/2 + 1/2
          n                n
  

  and n/2 + 1/2 is O(n).