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.
Unsorted
Ascending
Descending
Numbers
28 6 19 3
3 6 19 28
28 19 6 3
Words
fig pear apple
apple fig pear
pear fig apple
Worked examples
Order
Result
Unsorted
47 5 31 12
Ascending
5 12 31 47
Descending
47 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.
Position
1
2
3
4
5
6
Unsorted
Nodira
Leo
Amir
Tom
Lola
Ben
Ascending
Amir
Ben
Leo
Lola
Nodira
Tom
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 checked
9
14
22
31
40
Is it 40?
no
no
no
no
yes
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.
8, 9, 17, 45, 63, 120. The number 120 is the largest, even though it starts with 1.
2
Put these words in descending alphabetical order: pear, apple, mango, fig, lime.
pear, mango, lime, fig, apple. Descending alphabetical order goes from Z to A, so the word that is last in the alphabet comes first.
3
For each list, can a binary search for the value in the last column start straight away? Give a reason for each.
List
Items
Target
A
3 8 15 22 40
15
B
40 3 22 8 15
15
C
bear cow deer goat
deer
D
rat cat hen dog
hen
A: yes, because the numbers are in ascending order. B: no, because 40 is bigger than 3, so the numbers are not in order. C: yes, because the words are in alphabetical order. D: no, because rat, cat, hen, dog is not alphabetical, even though the word we want is there.
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.
The sorted list is 7, 19, 28, 34, 41, 52. In the original order a linear search for 41 checks 34, 7, 52, 19, 28 and then 41, so it checks 6 items. (41 is the last item in that order.)