Linear search

Searching means finding an element, called the key, in a collection: telling whether it is present and, if so, where.

Linear search (also called sequential or serial search) is the simplest method: compare the key with each element in turn, from the first to the last, until it is found or the list ends.

Example: searching for 17 in [8, -4, 7, 17, 0, 2, 19]: 8, -4 and 7 do not match; the 4th comparison matches, so 17 is found at position 4.

How many comparisons does it take, for a list of n elements?

• Best case: the key is the first element: just 1 comparison.
• Worst cases: the key is the last element, or not there at all: n comparisons.

Linear search does not need the list to be sorted, so it is useful for small and unordered lists. For large lists it becomes slow.

In Program 6-1, the function returns index + 1 as the position (since people count from 1, while list indexes start at 0), or None if the key is not present.