Linear search

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

F5.5AlgorithmsGCSE15 min

Covers OCR J277 2.1.3 Searching and sorting algorithms · AQA 8525 3.1.3 Searching algorithms · Edexcel 1CP2 1.2.6 Standard sorting and searching algorithms

Do this lesson in the simulator

Print it: worksheet (PDF) · answers (PDF) · as a web page

Guide: Linear search and binary search explained

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

  1. Start at the first item.
  2. If this item is the target, report where it is and stop.
  3. Otherwise move to the next item.
  4. 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.

Flowchart of linear search: set i to 0; while i is less than the length, check items[i]; output i if it is the target, otherwise add 1 to i and go round again; output -1 if the end is reachedStartInput items, targeti = 0i < lengthof items?Yesitems[i] ==target?YesOutput iEndNoi = i + 1NoOutput -1
The two ways out. Finding the target leaves straight away with its index (the green Yes), which is what return i does. Only when i reaches the end of the list with nothing found does the search output -1. The for loop is drawn as a count, i, with a decision and an update.

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.

The items linear search checks in the lesson's list for 12, 22, 40 and 99: 1, 5, 8 and 8 checks, and 99 is not there01234567indexfind 1212531822317401 checkfind 2212531822317405 checksfind 4012531822317408 checksfind 9912531822317408 checks, -1solid boxes are looked at; dashed ones never are
Each row is one search, from the left. The search stops at the green box, so the items after it are never looked at. 40 is the last item, so finding it takes every check, and so does 99, which is not there: only after checking all 8 can the search be sure.

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.

The eight headings the robot looks along: index 0 straight ahead, and each index 45 degrees further rightindex 00°index 145°index 290°index 3135°index 4180°index 5225°index 6270°index 7315°45° right
The robot starts facing index 0 and turns 45 degrees to the right after each look, so the position of a sighting in the list is also its direction: index times 45 degrees.

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.

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

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

Past paper questions on this

Real exam questions that test this, each worked through with a program you can run.