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= 0 2 repeat while
location< (length of the
list) 3 if
key4 print "Found at " +
location5 end program 6 set
location+ 1 advance to next location 7 8 print "Value not found"
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
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.
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.