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

Term 1 in review

Week 11 · Review: Term 1 · 3 lessons
3

Compare and search

Computing 9: Topics 1.1–1.7, pp. 11–134
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.

Worked examples
LineProgram QProgram R
1cm = int(input("cm? "))print(int(input("cm? ")) / 100)
2metres = cm / 100
3print(metres)
Variables20
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.
CheckItems still in playCentre item
13 7 12 18 25 31 40 52 66 79 8531
240 52 66 79 8566
379 8579
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.
SituationMethodReason
A sorted list of 5000 member numbersbinary searchhalving makes it far quicker
Five names in no particular orderlinear searchno sorting is needed
A list of prices, not in orderlinear searchbinary 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?
LineProgram SProgram T
1days = int(input("Days? "))days = int(input("Days? "))
2hours = days * 24print(days * 24)
3print(hours)
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.
Position12345678
Itemearthjupitermarsmercuryneptunesaturnuranusvenus
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?
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?