Linear Search

Linear search is the simplest searching algorithm. It finds an item, called the target, by checking the items in a list one after another, starting at the first item.

At each position, the search compares the current item with the target. If they match, it stops immediately and reports that the item has been found, including its position. If the current item does not match, the search moves on to the next item and repeats the comparison. The items are checked in sequence from the start, never in a random order or backwards.

A worked example

Suppose the locker numbers in a corridor are 6, 11, 4, 19 and 23, and you search for 19. The search compares 6 with 19, then 11 with 19, then 4 with 19, then 19 with 19. It stops at the fourth item and reports the match.

If the target had been 8, every one of the five items would have been compared before the search reached the end of the list and reported that 19 was not there. The search is only known to be unsuccessful once every item has been checked.

When it suits the job

Linear search does not need the data to be sorted, so it works on ordered or unordered data. It is simple to write, which makes it suitable for small lists, unsorted data and a search that will only be carried out once, where sorting first would add work for little benefit.

Its weakness is speed. If the target is near the end of a large list, or is not there at all, the search may have to check every item, so linear search is slow on large lists.

In Python, a linear search uses one index that starts at the first position and increases by one each time round a loop, comparing each item with the target as it goes.

lockers = [6, 11, 4, 19, 23]
wanted = 19

for position in range(len(lockers)):
    if lockers[position] == wanted:
        print("Found at position", position + 1)
        break

Output:

Found at position 4