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
3

Found, or not found?

Computing 8: Topic 1.3, pp. 59–69
GoalWrite a linear search for a short list and report both results: found at a position, or not found.
New words
report · to tell the user the result of a searchnot found · the result when the search reaches the end of the list with no matchunordered · not sorted: the items are in any order
Explanation

After a search, the program must report the result. When the target is found, it says where, for example Found at position 3. When the search reaches the end of the list without a match, it must say Not found. A program that stays silent leaves the user guessing. For a short list we can write a linear search as an IF statement with one ELSEIF for each position, and the final ELSE catches Not found. For long lists, programmers use iteration, which means a loop that repeats the same comparison, and that is a later topic. A linear search works on a list in any order, so the data does not need to be sorted. It is simple, but for very long lists it can be slow.

Pseudocode
1item1 ← "pen"
2item2 ← "ruler"
3item3 ← "glue"
4INPUT target
5IF item1 = target THEN
6    OUTPUT "Found at position 1"
7ELSEIF item2 = target THEN
8    OUTPUT "Found at position 2"
9ELSEIF item3 = target THEN
10    OUTPUT "Found at position 3"
11ELSE
12    OUTPUT "Not found"
13ENDIF
Worked examples
Target typeditem1 = targetitem2 = targetitem3 = targetOutput
rulerFalseTruenot checkedFound at position 2
glueFalseFalseTrueFound at position 3
eraserFalseFalseFalseNot found
The three items are pen, ruler and glue. For the target ruler the first comparison is False and the second is True, so the output is Found at position 2 and the third comparison is never checked. For glue it is Found at position 3. For eraser every comparison is False, so ELSE runs and the output is Not found.
Pseudocode
1item1 ← "pen"
2item2 ← "ruler"
3item3 ← "glue"
4INPUT target
5IF item1 = target THEN
6    OUTPUT "Found at position 1"
7ELSEIF item2 = target THEN
8    OUTPUT "Found at position 2"
9ELSEIF item3 = target THEN
10    OUTPUT "Found at position 3"
11ENDIF
Output
(nothing is shown for eraser)
Without the ELSE part, the program stays silent when the target is missing. With eraser typed, nothing is shown at all. The user cannot tell whether the search failed or the program broke.
FeatureRandom searchLinear search
order of lookingany orderfirst to last
can look at an item twice?yesno
sure to finish?not always quicklyyes, after at most one look at every item
needs sorted data?nono
Random search and linear search compared.
Class activity

Shelf search (no computer). Cut three slips of paper and write on each the name of a book or a toy: these are your shelves. Put the slips in a row, face down. Your partner says a target. Turn over the slips one at a time from the left, saying aloud what you compare each time, and finish with Found at position N or Not found. Do five rounds, including two targets that are not on the shelves. Then write the search as pseudocode with IF, ELSEIF and ELSE for your three words. If you have a computer or tablet, ask an adult to help you type it in Python with if, elif and else.

Practice
1
The user types atlas, then compass. What does the algorithm show each time?
Pseudocode
1shelf1 ← "map"
2shelf2 ← "atlas"
3shelf3 ← "globe"
4INPUT want
5IF shelf1 = want THEN
6    OUTPUT "Found at position 1"
7ELSEIF shelf2 = want THEN
8    OUTPUT "Found at position 2"
9ELSEIF shelf3 = want THEN
10    OUTPUT "Found at position 3"
11ELSE
12    OUTPUT "Not found"
13ENDIF
2
One line is missing from the algorithm. Write it.
Pseudocode
1shelf1 ← "map"
2shelf2 ← "atlas"
3shelf3 ← "globe"
4INPUT want
5IF shelf1 = want THEN
6    OUTPUT "Found at position 1"
7ELSEIF shelf2 = want THEN
8    OUTPUT "Found at position 2"
9ELSEIF _____ THEN
10    OUTPUT "Found at position 3"
11ELSE
12    OUTPUT "Not found"
13ENDIF
3
Write a linear search in pseudocode for three drinks of your own choice. It should report the position or say Not found.
4
Why must a search program say Not found, and why can a linear search be used on a list that is in no particular order?