Linear Search

Linear Search

• Also called Sequential Search.
• $WorstCase: T(n)$
• Implementation:

  for (int i = 0; i < len; i++) {      // Check length validity
    if (array[i] == elemToSearch)
        return i;
  }
  

Sentinel Linear Search (崗哨)

• Keep the element to be searched (elemToSearch) in the end, and to skip the array index searching. It's called sentinel value.
• To ensure that we can get matched index.
  • return index of sentinel value ⇒ search not found
  • return index other than sentinel value index ⇒ matched!
• Advantages:
  • Reduce overhead of checking if the index is within limit in each step. Reduce one comparison in each iteration.
  • Still $T(n)$, but faster than Linear Search w/o sentinel.
• Implementation:

  while(array[i] != elemToSearch) i++;
  while (array[i++] != elemToSearch) // do nothing;
  

References

• http://www.delorie.com/gnu/docs/avl/libavl_26.html