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

Halve and find

Week 10 · 1.7 Searching algorithms · 3 lessons
1

Put it in order

Computing 9: Topic 1.7, pp. 128–134
GoalPut numbers and words into ascending or descending order, and explain why a binary search needs data that is already in order.
New words
ascending · going up: from the smallest to the largest, or A to Zdescending · going down: from the largest to the smallest, or Z to Abinary search · a search that repeatedly checks the centre of a sorted list and throws away half of the data
Explanation

A searching algorithm looks for one item in a set of data. A linear search checks the items one at a time, from the first, until it finds the item or runs out of items. A binary search is a different method, and it can be much faster, but it has a strict rule: the data must be in order before it starts. Ascending order goes from small to large, such as 3, 8, 15, or from A to Z. Descending order goes the other way. In this lesson the lists are in ascending order. Numbers are put in order by size, so 9 comes before 12. Words are put in alphabetical order, comparing the first letter, then the second if the first letters match. So lemon comes before lime, because e comes before i.

UnsortedAscendingDescending
Numbers28 6 19 33 6 19 2828 19 6 3
Wordsfig pear appleapple fig pearpear fig apple
Worked examples
OrderResult
Unsorted47 5 31 12
Ascending5 12 31 47
Descending47 31 12 5
Sorting numbers. The unsorted numbers are 47, 5, 31 and 12. Ascending order starts with the smallest, 5, and ends with the largest, 47. Descending order is the same list read from the other end. Notice that 5 comes before 12 because 5 is smaller. It does not matter that 12 starts with a smaller digit.
Position123456
UnsortedNodiraLeoAmirTomLolaBen
AscendingAmirBenLeoLolaNodiraTom
Sorting words. The names are Nodira, Leo, Amir, Tom, Lola and Ben. Alphabetical order puts Amir first. Leo and Lola both start with L, so look at the second letter: e comes before o, so Leo comes before Lola.
Item checked914223140
Is it 40?nonononoyes
A linear search needs no order, but it can be slow. The list is 9, 14, 22, 31, 40, 58, 63 and 77, and the target is 40. The search checks 9, 14, 22, 31 and then 40, so it makes 5 checks. If the target was 50, which is not in the list, it would have to check all 8 items before it could say not found.
Class activity

Card line (no computer). Write eight numbers between 1 and 99 on eight small cards, and shuffle them. Put the cards in a row, face down. Do a linear search for a number that your partner names: turn the cards over from the left, one by one, and count the cards you turn. Now turn all the cards up, put them in ascending order, and think: where would you look first if you knew the cards were in order? Explain why this idea only works when the cards are sorted.

Practice
1
Put these numbers in ascending order: 63, 8, 120, 45, 17, 9.
2
Put these words in descending alphabetical order: pear, apple, mango, fig, lime.
3
For each list, can a binary search for the value in the last column start straight away? Give a reason for each.
ListItemsTarget
A3 8 15 22 4015
B40 3 22 8 1515
Cbear cow deer goatdeer
Drat cat hen doghen
4
Write the list 34, 7, 52, 19, 28, 41 so that a binary search can be used on it. Then say how many items a linear search for 41 would check in the unsorted list.