Linear search

Checking every item: finding a marker in the robot's sightings.

F5.5AlgorithmsGCSE15 min

Searching is one of the jobs computers do most: finding a name in a contact list, a word in a document, a marker in a robot's camera log. The simplest search algorithm looks at every item in turn until it finds the one it wants. That is linear search, and this lesson has the robot use it to find a marker in a ring around it.

The algorithm

Start at the first item.
If this item is the target, report where it is and stop.
Otherwise move to the next item.
If there are no items left, report that the target is not there.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def linear_search(items, target):
    """Return the index of target in items, or -1 if it is not there."""
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

ids = [12, 5, 31, 8, 22, 3, 17, 40]
print(linear_search(ids, 22))
print(linear_search(ids, 99))

Run this in the simulator

return i stops the search as soon as the target is found, so nothing after it is checked. If the loop gets all the way to the end, the target is not there and the function returns -1, a value that can never be a real index.

Counting the work

How much work a search does is measured in comparisons: how many items it has to look at.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def linear_search(items, target):
    checks = 0
    for i in range(len(items)):
        checks = checks + 1
        if items[i] == target:
            return i, checks
    return -1, checks

ids = [12, 5, 31, 8, 22, 3, 17, 40]
for target in [12, 22, 40, 99]:
    print("looking for", target, "gives", linear_search(ids, target))

Run this in the simulator

The first item takes 1 check. The last takes 8. An item that is not there takes 8 too, because every item must be checked to be sure. With a list of a million items, the worst case is a million checks. Linear search is simple and works on any list, sorted or not, but for big lists it is slow.

Searching what the robot sees

The robot stands in the middle of a ring of eight markers, 45 degrees apart. The camera reads marker numbers with marker_tags(), which gives each marker in view as [id, cx, cy, distance]. The one straight ahead has cx near 160, the middle of the picture.

First the robot builds a list of sightings: which marker is straight ahead at each heading. Then linear search finds the one it wants:

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

set_cv("apriltag")

def ahead_id():
    """The id of the marker straight ahead, or None."""
    for tag in marker_tags():
        if abs(tag[1] - 160) < 30:
            return tag[0]
    return None

sightings = []
for i in range(8):
    sightings.append(ahead_id())
    turn_right(30, angle=45)
print("sightings:", sightings)

Run this in the simulator

The list's index says which direction each marker is in: index 2 is 2 times 45 degrees, facing 90. So finding marker 8 means searching sightings for 8 and turning to its index times 45.

When linear search is the right choice

The list is not sorted, or sorting it would cost more than the search saves.
The list is short, so the difference hardly matters.
You only search it once.

The next lesson meets a search that is far faster, but only works on sorted data.

In the exam

You may be asked to describe linear search, write it in pseudocode or code, show the steps it takes to find an item in a given list, or give its advantages and disadvantages. Its advantage: it works on unsorted data and is simple. Its disadvantage: it is slow on large lists, because in the worst case every item is checked.

OCR 2.1.3

The standard searching algorithms are linear search and binary search. OCR asks you to understand the main steps of each, apply them to a set of data, and identify an algorithm from its code.

AQA 3.1.3

AQA asks you to understand and explain how linear search and binary search work, and to compare them: linear search works on unsorted data, binary search is more time efficient on sorted data.

Edexcel 1.2.6

Edexcel lists linear search and binary search among the standard algorithms you should be able to explain and use.

Task: find the marker

The task asks Which marker? and answers 31. Look in all eight directions and record the marker straight ahead in each, then use linear search on your list to find where the wanted marker is. Print found <id> at <degrees> degrees after <n> checks, turn to face it, and beep.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

set_cv("apriltag")
target = int(input("Which marker? "))

Challenges

Change the search to find every position of a target in a list that has repeats, and return a list of indexes.
Search a list of names for the first one that starts with a given letter.
What does the search report if two markers in the ring had the same id? Is that a problem?