GoalReview comparing algorithms and binary search: judge two programs, and find or fail to find an item in sorted data.
New words
efficiency · how little memory, effort or time a program needs to do its jobrobust · less likely to give wrong answers or crash on odd inputbinary search · a search that checks the centre of sorted data and discards half each timeascending · in order from smallest to largest, or A to Z
Explanation
To compare two programs, first check the requirements. A program that fails a requirement is out. Next, compare efficiency, for example by counting variables, which use memory, or the passes through a loop. Say which program is better and give reasons. A robust program is one that checks the data before it uses it. A linear search checks items one at a time, so it works on any list. A binary search needs sorted data. It compares the target with the centre item, discards the centre and the half that cannot hold the target, and repeats until the target is found or nothing is left. When the number of items is even, choose one middle item by a rule and keep to it.
Check the requirementsonly programs that work→Compare the efficiency→Choose and give reasons
Worked examples
Line
Program Q
Program R
1
cm = int(input("cm? "))
print(int(input("cm? ")) / 100)
2
metres = cm / 100
3
print(metres)
Variables
2
0
Comparing two programs. The requirement is to ask for a length in centimetres and output it in metres. Both programs print 2.5 when the user types 250. Program Q uses a variable for the answer and program R does not, so R is more efficient with memory. Q is easier to read.
Check
Items still in play
Centre item
1
3 7 12 18 25 31 40 52 66 79 85
31
2
40 52 66 79 85
66
3
79 85
79
A binary search for 79. The sorted list has eleven items, so the centre is the sixth item, 31. 79 is larger, so 31 and the left part go. Five items are left, and the centre is 66. 79 is larger again, so 79 and 85 remain. The left middle one is 79, so it is found after 3 comparisons.
Situation
Method
Reason
A sorted list of 5000 member numbers
binary search
halving makes it far quicker
Five names in no particular order
linear search
no sorting is needed
A list of prices, not in order
linear search
binary search would give wrong answers
Choosing the search. A linear search works on any list, while a binary search needs the data sorted. Pick the method that fits, and say why.
Class activity
Price tags (no computer). Write the numbers 6, 14, 19, 27, 33, 41, 58 and 64 on cards and put them in order. Give a partner a target number. They search with a binary search and cover the discarded cards with paper. Count the comparisons. Now ask for a number that is not on the cards, such as 30, and decide how they know it is not there. Finally, shuffle the cards and ask if the same method still works.
Practice
1
The requirement is: ask for a number of days and output the number of hours. Both programs print 72 when the user types 3. Which is more efficient, and why? Which is easier to read, and why?
Line
Program S
Program T
1
days = int(input("Days? "))
days = int(input("Days? "))
2
hours = days * 24
print(days * 24)
3
print(hours)
Program T is more efficient, because it uses one variable and program S uses two. S is easier to read, because the name hours says what the value means.
2
Use a binary search in this sorted list, taking the left of two middle items. Look for saturn, then for moon. Write the centre item at each check, the result, and the number of comparisons.
Position
1
2
3
4
5
6
7
8
Item
earth
jupiter
mars
mercury
neptune
saturn
uranus
venus
saturn: centre mercury; saturn comes after it, leaving neptune saturn uranus venus; the centre is saturn, so it is found after 2 comparisons. moon: centre mercury; moon comes after it (o comes after e), leaving neptune saturn uranus venus; centre saturn; moon comes before it, leaving neptune; moon comes before neptune and nothing is left. Not found, after 3 comparisons.
3
Ravi wants to use a binary search on the list 40, 12, 33, 7, 25. He says: ‘The centre is 33, so I can start.’ What should he do first? Why?
He must put the list in ascending order first: 7, 12, 25, 33, 40. A binary search only works when the data is sorted. In the unsorted list, discarding half could throw away the target.
4
A sorted list has 100 items. At most how many comparisons could a binary search need? At most how many checks could a linear search need? Why is the binary search so much quicker?
A binary search needs at most 7 comparisons, and a linear search could need 100 checks. Every comparison in a binary search throws away about half of the data that is left.