• LinearSearch

The linear (or sequential) search is the simplest search algorithm of all. It merely searches every member of a data set for a certain value until it is found, linearly. It has a linear run time and is entirely ok for usage with small data sets (note the emphasis on the small). It is also useful for unordered data.

The steps performed by a linear search are (assuming you have a list-to-be-searched, an item-to-be-found, and an equality-predicate)

1. Check to see if the list is empty. If it is, return false.
2. Compare the current item in the list-to-be-searched with the item-to-be-found using the equality-predicate.
3. If the equality-predicate returns true, then return true. Otherwise,
4. Return to step 1, setting the head of the list-to-be-searched to the next item in the list.

An example implementation (in Scheme):

(define (linear-search list-to-be-searched item-to-be-found
                       equality-predicate?)
  (cond ((null? list-to-be-searched)
         #f) ; item not found
        ((equality-predicate? (car list-to-be-searched) item-to-be-found)
         #t) ; item found
        (else
         (linear-search (cdr list-to-be-searched) item-to-be-found
                        equality-predicate?))))

Calling (linear-search '(1 2 3) 2 =) will return true because "2" is in the list-to-be-searched and matches the equality-predicate (which is the numerical equality function). This could be modified to return the index of the item found by looping over the list intead of recursing through it. Another useful modification would be to return the item found in the list for possible modification.