Linear Search

The linear search is used to find an item in a list. The items do not have to be in order. To search for an item, start at the beginning of the list and continue searching until either the end of the list is reached or the item is found.

The algorithm is as follows (given a list called 'List' and looking for an item called 'item'):

1
2
3
4
5
6
position <- 0
found <- False
while position < len(List) and not found:
    if List[position] = item:
        found <- True
    position <- position + 1

This video clip shows how to write a linear search in Python:


Exercises

  1. Implement the linear search as described in the video and using the algorithm. Test that it works with items in and not in the list
  2. Add a counter to report how many searches have been done for each item searched for.
  3. Add the functionality to add an item to the list if it is not found.