Practical Programming, 3rd Edition

Searching a List

As you have already seen in Table 11, ​List Methods​, Python lists have a method called index that searches for a particular item:

index(...)
    L.index(value, [start, [stop]]) -> integer -- return first index of value

List method index starts at the front of the list and examines each item in turn. For reasons that will soon become clear, this technique is called linear search. Linear search is used to find an item in an unsorted list. If there are duplicate values, our algorithms will find the leftmost one:

>>> ['d', 'a', 'b', 'a'].index('a')
1

We’re going to write several versions of linear search in order to demonstrate how to compare different algorithms that all solve the same problem. ...