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
2

Find the middle

Computing 9: Topic 1.7, pp. 128–134
GoalCarry out a binary search on a sorted list, step by step, and count the comparisons.
New words
centre item · the item in the middle of the data that is still being searcheddiscard · to throw away data that cannot hold the targetcomparison · one check of the target against an item
Explanation

A binary search works on sorted data. Here are the steps. Step 1: find the centre item of the data that is left. If there is an even number of items, there are two middle ones; this course always takes the left one, and you can use either side as long as you never change your choice. Step 2: compare the target with the centre item. If they are equal, you have found it. Step 3: if the target is smaller than the centre item, discard the centre item and everything to its right, because those items are all larger. If the target is larger, discard the centre item and everything to its left. Step 4: repeat with the data that is left. Stop when you find the target, or when there is nothing left, which means the target is not in the list. Each check against a centre item counts as one comparison.

Worked examples
CheckItems still in playCentre itemCompareDecision
14 9 15 22 31 38 46 53 673153 > 31discard 31 and everything to its left
238 46 53 674653 > 46discard 46 and everything to its left
353 675353 = 53found
The sorted list is 4, 9, 15, 22, 31, 38, 46, 53 and 67, and the target is 53. There are nine items, so the centre is the fifth item, 31. Because 53 is larger, the left half and 31 are discarded. Four items are left, so the left middle one is 46. Again 53 is larger, so 46 and the left part go. Two items are left, and the left one is 53, which is the target. The search makes 3 comparisons.
CheckItems still in playCentre itemCompareDecision
14 9 15 22 31 38 46 53 67319 < 31discard 31 and everything to its right
24 9 15 2299 = 9found
The same list, but the target is 9. The first centre is 31 again. This time 9 is smaller, so 31 and everything to its right are discarded. The four items 4, 9, 15 and 22 are left. The left middle item is 9, so the target is found after 2 comparisons.
TargetComparisonsResult
311found
92found
533found
674found
Different targets in the same list. The number of comparisons depends on where the target is. A lucky target in the centre is found at once. The largest item takes the most comparisons here. A linear search for 67 would check all nine items.
Class activity

Cover and reveal (no computer). Write the sorted numbers 3, 8, 14, 21, 27, 35, 42, 56 and 61 on nine strips of paper in a row. Your partner chooses a secret target and tells you only whether it is in the list. Find it by a binary search: point at the centre strip, ask ‘Is the target equal, smaller or larger?’, and cover the half you can discard. Count your comparisons. Swap roles and use a new target.

Practice
1
The sorted list is 6, 15, 24, 33, 42, 51, 60. Use a binary search to look for 51. Write a table with the items in play and the centre at each check. How many comparisons are needed?
CheckItems still in playCentre item
16 15 24 33 42 51 60?
2??
2
Use the same list, 6, 15, 24, 33, 42, 51, 60, to look for 6. List the centre item at each check and say how many comparisons are needed.
3
The list has an even number of items: 2, 8, 14, 20, 26, 32. Always take the left of the two middle items. Which item is checked first? Look for 26 and count the comparisons.
Position123456
Item2814202632
4
Kai looks for 70 in 10, 20, 30, 40, 50, 60, 70. He writes: ‘Centre is 40. 70 is larger than 40, so I discard the right half.’ Find the mistake, then finish the search correctly and count the comparisons.