Found, or not found?
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.
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
| Target typed | item1 = target | item2 = target | item3 = target | Output |
|---|---|---|---|---|
| ruler | False | True | not checked | Found at position 2 |
| glue | False | False | True | Found at position 3 |
| eraser | False | False | False | Not found |
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
(nothing is shown for eraser)
| Feature | Random search | Linear search |
|---|---|---|
| order of looking | any order | first to last |
| can look at an item twice? | yes | no |
| sure to finish? | not always quickly | yes, after at most one look at every item |
| needs sorted data? | no | no |
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.
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
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