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
1

Hunting through the data

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

1?2?3?4?5?
Worked examples
TaskData that is searchedTarget
call a friend from a phonethe list of contactsthe friend’s name
borrow a bookthe library cataloguethe book title
find the next busthe timetablethe name of the town
Three everyday searches. Each one has a collection of data and a target.
12✗3✓4✗5✗
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.
1✗2✗3✓45
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.
2
A linear search looks for 8 in this row of numbers. Which positions are looked at, and how many looks does it need?
Position12345
Item12530817
3
Why can a random search take longer than a linear search of the same five bags? Give two reasons.
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.