Linear Search concepts

Linear search is the most fundamental and important of all algorithms.


The input to linear search is a sequence (e.g. an array, a collection, a string, an iterator, etc.) plus a target item. The output is true if the target item is in the sequence, and false otherwise. If the sequence has n items, then, in the worst case, all n items in the sequence must be checked against the target for equality. Under reasonable assumptions, linear search does O(n) comparisons on average. In practice, this is often too slow, and so, for example,  BinarySearching or hashing or TreeSearching are speedier alternatives.

Here's an implementation of linear search on an array (in Java):

  // returns true iff there is an integer i, where arr[i] == target and 0 <= i < arr.length
  boolean linearSearch(int[] arr, int target)
  { 
 int i = 0;
 while (i < arr.length) {
   if (arr[i] == target) {
  return true;
   } // if 
   ++i;
 } 
 return false;
  }

Linear search can be sped up through the use of a sentinel value: assuming there is a free cell at the end of arr to use, then copy target into that free cell. This lets you move the test ``i < arr.length'' out of the loop. For example:

  // PRE: arr[arr.length - 1] == target
  // POST: returns true iff there is an integer i, where arr[i] == target and 0 <= i < arr.length - 1
  boolean _fastLinearSearch(int[] arr, int target)
  { 
 int i = 0;
 while (arr[i] != target) {  // only one comparison per iteration
   ++i;
 } 
 return i < arr.length;
  }



  // returns true iff there is an integer i, where arr[i] == target and 0 <= i < arr.length
  boolean fastLinearSearch(int[] arr, int target)
  {  
 int n = arr.length;
 if (arr[n - 1] == target) {  // is target at the end?
   return true;
 } else {
   int last = arr[n - 1];  // remember the final value of the array
   arr[n - 1] = target;
   boolean result = _fastLinearSearch(arr,target);
   arr[n - 1] = last; // restore the array
   return result;
 } // if
  }

e.g.:

 int target = ...;



 boolean found = false;
 int i = arr.length-1;



 while (i >= 0) {  // comparison 1
 if (arr[i] == target) { // comparison 2
 found = true;
 break;
 }
 i--;
 }

This code does two comparisons per iteration - it checks "i >= 0" and also "arr[i] == target". The fastLinearSearch code does only 1 comparison each time around the loop, since using a sentinel moves one comparison outside of the loop, hence speeding it up. Count the number of comparisons done in fastLinearSearch and you'll see.