GoalExplain why programs search, and describe how a random search and a linear search work.
New words
searching algorithm · a set of steps for finding an item in a collection of datarandom search · looking at items in any order, with no plan, until the item is foundlinear search · looking at the items one after another, in order, from the first to the lasttarget · the item that is being looked for
Explanation
Programs search all the time. A phone looks for a name in its contacts, a library system looks for a book title and a train app looks for the next train to a town. A searching algorithm is a set of steps for finding an item in a collection of data, and the best one depends on the data. A random search picks any item, looks at it and repeats until the target is found. It may look at the same item twice, so it can take a long time. A linear search is more careful. It begins with item one, moves on to item two and then item three, always in order, and never returns to an item it has seen. Both searches look at only one item at a time.
Worked examples
Task
Data that is searched
Target
call a friend from a phone
the list of contacts
the friend’s name
borrow a book
the library catalogue
the book title
find the next bus
the timetable
the name of the town
Three everyday searches. Each one has a collection of data and a target.
A random search. Five bags hold a key, scissors, a cup, a book and a pencil. The target is the cup. A random search happens to open bag 4, then bag 2, then bag 4 again, then bag 5, and at last bag 3. It wasted time opening bag 4 twice.
A linear search of the same bags. It opens bag 1 (a key, not the cup), bag 2 (scissors, not the cup) and bag 3 (the cup). It stops there after three looks, and it never opens a bag twice.
Class activity
Cup game (no computer). Take six paper cups or six sheets of paper in a row. Under each one hide a small slip with a different number from 1 to 20. Your partner chooses a target number and says it out loud. First search at random: point to any cup, lift it, look, put it back, and count your looks (you may pick the same cup twice). Then search in a line from the first cup to the last, counting your looks. Repeat with three different targets. Which search used fewer looks? Which one is easier to explain to someone else? If you have a computer or tablet, ask an adult to show you how a contact list finds a name.
Practice
1
Name three searches that a computer might do at a shop till, in a school register and in a music player. For each, say what data is searched and what the target is.
For example: a till searches the product list for a bar code (target: the code). A register program searches the pupil list for a name. A music player searches the song list for a title. Any three sensible answers are correct.
2
A linear search looks for 8 in this row of numbers. Which positions are looked at, and how many looks does it need?
Position
1
2
3
4
5
Item
12
5
30
8
17
Positions 1, 2, 3 and 4 are looked at (12, 5, 30 and 8). It stops at position 4, because 8 is found there. That is 4 looks.
3
Why can a random search take longer than a linear search of the same five bags? Give two reasons.
A random search may open the same bag more than once, and it has no plan, so it can miss the right bag for many turns. A linear search opens each bag at most once, so it needs at most 5 looks.
4
Say whether each statement is true or false and correct the false ones. (a) A linear search can start at any bag. (b) A linear search looks at one item at a time. (c) A random search never looks at an item twice.
(a) False: it starts at the first item. (b) True. (c) False: a random search may look at the same item more than once.