Tracing a Linear Search

Tracing a linear search means writing out every comparison the algorithm makes, in order, so that a reader can follow the search from start to finish. The marks come from showing each check you make, not just the final answer.

Laying out each comparison

Linear search always starts at the first item and moves along one item at a time, so your trace must do the same: no jumping ahead, no starting in the middle, no skipping items that look unlikely. A tidy way to write it is one row per comparison, showing the position being checked, the value stored there, and whether it matches.

Take these locker numbers along a corridor: 38, 47, 56, 33, 41, 24. Searching for 33, counting positions from 1:

The search stops here, after four comparisons, and reports position 4. It does not check 41 or 24, because once a match is found any further comparison is wasted work. Always end a successful trace with that reported position.

A program that prints each comparison as it goes looks like this:

locker_numbers = [38, 47, 56, 33, 41, 24]
wanted_number = 33
place = 0
match_position = -1

while place < len(locker_numbers) and match_position == -1:
    print("Position", place + 1, "holds", locker_numbers[place])
    if locker_numbers[place] == wanted_number:
        match_position = place + 1
    place = place + 1

if match_position == -1:
    print("Not found")
else:
    print("Found at position", match_position)

Output:

Position 1 holds 38
Position 2 holds 47
Position 3 holds 56
Position 4 holds 33
Found at position 4

Position or value?

The position is where an item sits; the value is what is stored there. In the list above, position 4 holds the value 33, so the two numbers are different. Say up front whether you are counting positions from 0 or from 1, then keep to it, since a list counted from 0 would put 33 at position 3. A trace that mixes the two, or that reports the value when asked for a position, is wrong even when the comparisons are right.

When the item is not there

An unsuccessful trace lists every item being compared, one after another, right through to the last one. Only then can you say that the end of the list has been reached and the item is not present. Searching the same list for 50 gives six comparisons, all mismatches, and then the report of not found. That closing statement matters: until every position has been checked, all you know is that the item has not turned up yet, not that it is absent.