AdvertisementYour brand could be hereYour brand hereOn every Darslab page · students, parents and teachersinfo@darslab.comAsk for pricesPricesinfo@darslab.com
☰ Year plan · Computing

Finding the one item

Week 5 · 1.3 Searching algorithms · 3 lessons
2

One look at a time

Computing 8: Topic 1.3, pp. 59–69
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.

StepWhat the search does
1Start at position 1
2Compare the item with the target
3If it matches: stop and report the position
4If not: move to the next position and go back to step 2
5If there are no more items: report that the target is not there
Worked examples
PositionItemIs it radish?
1carrotno
2beanno
3peano
4lettuceno
5radishyes
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.
TargetPositions looked atLooksResult
271, 2, 3, 4, 55found at 5
91, 2, 3, 4, 5, 66found at 6
1411found at 1
401, 2, 3, 4, 5, 66not 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 item1
fourth item4
last item8
not in the list8
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?
Position123456
NameLolaAmirAnaChenYukiOmar
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.
Position123456
Item622918403
3
A list has 20 items. What is the most looks a linear search can need, and when? What is the fewest?
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.