Finding the one item
Answers are for parents and teachers.
1
Trace a linear search for pea in the list below. Write the positions looked at and the number of looks.
| Position | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| Item | rose | daisy | pea | tulip | lily |
Positions 1, 2 and 3 are looked at (rose, daisy, pea). It stops at position 3 after 3 looks.
2
A list holds 9 names. A linear search looks for a name that is NOT in the list. How many names does it look at, and what must the program show?
It looks at all 9 names and then shows Not found.
3
Describe how you would find a friend’s name in a printed class list with a linear search. Write the steps.
Start at the first name. Compare it with the friend’s name. If it matches, stop and say the position. If not, move to the next name and repeat. If you reach the end of the list, say Not found.
4
Give one advantage and one disadvantage of a linear search.
Advantage: it is simple and works on a list in any order. Disadvantage: for a very long list it can take many looks, because the worst case is that every item is looked at.
5
Write one reason why a search engine, a log-in screen or a library catalogue needs a searching algorithm.
They all hold a very large amount of data and must find the one item or the few items the user asks for. Without a search algorithm the program could not find a match.