8.2. Linear Search

Computers spend lots of time working with large lists of data. One of the fundamental tasks they do with that data is to search it for particular values - say looking up a particular student record so it can be displayed.

What is the simplest method for searching a list of elements? Check the first item, then the second item, and so on until you find the target item or reach the end of the list. Because we progress in a straight line through the list items, it is known as a linear search. Of course, to be an effective algorithm, we have to specify it in terms of operations a computer can do.

Assume a list called list, filled with integers. Each integer in the list has a unique location in the list - called its index. The task is to search for the location of a particular value - often called the key. Here’s how to search for the location of key in list:

    Note: assume that list and key are already set
1   set location = 1
2   repeat until location > (length of the list)
3       if list[location] == key
4           print "Found at " + location
5           end program
6       set location = location + 1     advance to next location
7
8   print "Value not found"

Note that location here is a variable that stores the index we are currently looking at in the list. list[location] is the standard way of saying “the value in list at location”.

You can try doing a linear search below. Type the number you wish to search for in the text box, then step through the search. Each “Step” in the animation takes you through the repeat loop one time. Try following the algorithm above step by step as you watch the animation.

Value to search for (key): Step Reset

Animation based on work by Y. Daniel Liang

Linear search is pretty easy, but it does have one big weakness - you potentially have to look at every item in the list. Imagine finding someone’s number in a phone book with linear search! While linear search works fine for small jobs, it does not scale well to larger problems.

You have attempted of activities on this page