Linear Search

A linear search finds a target value in a collection by checking the items one at a time, from the first item onwards. It does not need the data to be sorted: the same method works on a jumbled list of values or on one held in alphabetical or numerical order, because it simply takes the items in the order they appear.

The search always begins at the first item and compares it with the target:

• If the two match, the search stops and reports success.
• If they do not match, the search moves to the next item and compares again.
• If the search reaches the end of the collection without a match, it reports that the target is not present.

Stopping as soon as a match is found matters: there is no reason to keep checking items once the target has been located, and reporting the position of the match is often just as useful as knowing it exists.

A worked example

Suppose a bag holds six raffle tickets, and you want to know whether ticket 29 has been drawn. The tickets are in the order 41, 17, 63, 8, 29 and 55.

The search stops at the fifth ticket and can report that ticket 29 was found at position 5. If the target had been 12, every ticket would be checked and the search would report that 12 is not in the bag. Positions can also be counted from 0, as Python does, so the matching ticket has index 4.

Linear search in Python

def linear_search(tickets, target):
    position = 0
    for ticket in tickets:
        if ticket == target:
            return position
        position = position + 1
    return -1

raffle = [41, 17, 63, 8, 29, 55]
print(linear_search(raffle, 29))
print(linear_search(raffle, 12))

Output:

4
-1

The loop checks each ticket in turn and keeps count of how many it has passed. As soon as the ticket being compared equals the target, the subprogram returns that position and the search ends. If the loop runs out of tickets, the subprogram returns -1, showing that the target was not found.