Worksheet

F5.5 Linear search

Algorithms · GCSE · OCR J277 2.1.3, AQA 8525 3.1.3, Edexcel 1CP2 1.2.6 · about 15 min

What this lesson is about

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

• The algorithm
• Counting the work
• Searching what the robot sees
• When linear search is the right choice

Questions 5 marks in all

1. [1 mark]Linear search looks for 22 in [12, 5, 31, 8, 22, 3]. How many items does it check?

2. [1 mark]Linear search looks for 99 in a list of 8 items that does not contain it. How many items does it check?

3. [1 mark]Does linear search need the list to be sorted?

   1. ANo, it works on any list
   2. BYes, always
   3. COnly for numbers
   4. DOnly for long lists

4. [1 mark]What is the main disadvantage of linear search?

   1. AIt is slow on large lists
   2. BIt needs sorted data
   3. CIt cannot find the first item
   4. DIt uses a lot of memory

5. [1 mark]What does this program print?

   def find(items, target):
       for i in range(len(items)):
           if items[i] == target:
               return i
       return -1
   
   print(find([4, 9, 2], 2), find([4, 9, 2], 7))

The 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? "))

Plan your program here, then type it in and press Run.

Do it on the robot
www.bugbotlab.com/learn/f5-5-linear-search/
The simulator checks it and tells you when it passes. Nothing to install, no account.

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?