GoalTrace a linear search with a table and count how many items are looked at.
New words
position · the place of an item in a list: 1 for the first, 2 for the second and so oncompare · check whether an item is the same as the targetmatch · an item that is the same as the targetbest case / worst case · the fewest, or the most, looks a search could need
Explanation
In a linear search the program starts at position 1. It compares that item with the target. If they match, the search stops and reports the position. If they do not match, it moves on to the next position and compares again. It carries on until it finds a match or reaches the end of the list. To trace a linear search, make a table with the position, the item and whether it matches. The number of items looked at is the number of rows you filled in. The best case is that the target is first, so there is only one look. The worst case is that it is last or not there, and then every item is looked at.
Step
What the search does
1
Start at position 1
2
Compare the item with the target
3
If it matches: stop and report the position
4
If not: move to the next position and go back to step 2
5
If there are no more items: report that the target is not there
Worked examples
Position
Item
Is it radish?
1
carrot
no
2
bean
no
3
pea
no
4
lettuce
no
5
radish
yes
A gardener keeps seed packets in a row: carrot, bean, pea, lettuce, radish, squash. The target is radish. The trace table shows five rows, so five items are looked at, and the search stops at position 5.
Target
Positions looked at
Looks
Result
27
1, 2, 3, 4, 5
5
found at 5
9
1, 2, 3, 4, 5, 6
6
found at 6
14
1
1
found at 1
40
1, 2, 3, 4, 5, 6
6
not found
Different targets in the number list 14, 8, 31, 5, 27, 9. The last target is not in the list, so every item is looked at before the search reports that it is missing.
Where is the target?
Looks needed
first item
1
fourth item
4
last item
8
not in the list
8
For a list of 8 items, the number of looks depends on where the target is. The best case is 1 look and the worst case is 8.
Class activity
Row of cards (no computer). Write eight different words or numbers on eight cards, mix them and lay them in a row, each one hidden under a paper cup. Your partner names a target. Lift the cups one at a time from the left and draw a trace table (position, item, match?) as you go. Count the looks. Then ask your partner to put the target in the first place and the last place and compare the counts. Swap roles twice. Write one sentence about the best case and one about the worst case. If you have a computer or tablet, ask an adult to type the list into a spreadsheet and look for a target by eye.
Practice
1
A linear search looks for Chen. Complete a trace table. Which positions are looked at, and how many looks are needed?
Position
1
2
3
4
5
6
Name
Lola
Amir
Ana
Chen
Yuki
Omar
Positions 1 (Lola), 2 (Amir), 3 (Ana) and 4 (Chen) are looked at. Chen is found at position 4 after 4 looks. Yuki and Omar are never looked at.
2
In the list below, how many looks does a linear search need for the targets 40, 22 and 7? Say if each is found.
Position
1
2
3
4
5
6
Item
6
22
9
18
40
3
40: 5 looks, found at position 5. 22: 2 looks, found at position 2. 7: 6 looks, because every item is looked at, and it is not found.
3
A list has 20 items. What is the most looks a linear search can need, and when? What is the fewest?
The most is 20, when the target is last or is not in the list. The fewest is 1, when the target is the first item.
4
A pupil says: I searched for 18 in the list 6, 22, 9, 18, 40. I saw that 18 is at position 4, so I looked at only 2 items. Explain the mistake.
A linear search cannot skip items. It must look at 6, 22, 9 and then 18, so it needs 4 looks. The pupil used the answer they could see instead of following the search steps.