Linear Search in Python

In Python, a linear search is built from one loop with a single index that starts at the first position and moves one place at a time, comparing each item with the one you are looking for until it finds a match or reaches the end of the list. That steady, one-place-at-a-time movement is what makes it easy to recognise.

The variables that give it away

A linear search needs an index (often named index) that starts at 0 and has 1 added to it at the end of every pass around the loop, so each item is visited exactly once, in order. Alongside it sit two more variables:

• A found flag, set to False before the loop and changed to True only when a match is made, so the code after the loop knows what happened.
• A position variable, given the value of the index at the moment of a match, so the search can report where the item was.

Give the position a starting value that could not be a real position, such as -1. The flag, not the position, decides what happens after the loop, so an unsuccessful search reports that the item is missing rather than printing a made-up position.

The loop and its condition

The loop has two jobs: reach every position, and stop early once the item is found. The condition index < len(tickets), together with a check that the flag is still False, does both. The first part keeps the index inside the list, and the second part ends the search the moment a match is made, so later items are never compared.

tickets = [104, 219, 337, 452, 588, 601]
wanted = 452
was_found = False
position = -1
index = 0
while index < len(tickets) and was_found == False:
    if tickets[index] == wanted:
        was_found = True
        position = index
    index = index + 1
if was_found == True:
    print("Ticket", wanted, "was found in slot", position)
else:
    print("Ticket", wanted, "is not in this list")

Output:

Ticket 452 was found in slot 3

After the loop, a single if statement tests the flag: True prints the position, and False prints that the item is not in the list.

Getting the loop bounds right

In a list of six items the positions are 0 to 5, so the last valid index is the length minus one and the loop must run while the index is < len(...). Writing <= instead lets the index reach 6, and the next comparison reads past the end of the list.

scores = [14, 27, 31, 46, 58, 69]
wanted = 99
was_found = False
index = 0
while index <= len(scores) and was_found == False:
    if scores[index] == wanted:
        was_found = True
    index = index + 1
print(was_found)

Output:

IndexError: list index out of range (line 6)