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.
Find the centre item→Compare with the targetequal→Found? Stopsmaller or larger→Discard halfagain→Repeat with the rest
Worked examples
Check
Items still in play
Centre item
Compare
Decision
1
4 9 15 22 31 38 46 53 67
31
53 > 31
discard 31 and everything to its left
2
38 46 53 67
46
53 > 46
discard 46 and everything to its left
3
53 67
53
53 = 53
found
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.
Check
Items still in play
Centre item
Compare
Decision
1
4 9 15 22 31 38 46 53 67
31
9 < 31
discard 31 and everything to its right
2
4 9 15 22
9
9 = 9
found
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.
Target
Comparisons
Result
31
1
found
9
2
found
53
3
found
67
4
found
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?
Check
Items still in play
Centre item
1
6 15 24 33 42 51 60
?
2
?
?
Check 1: items 6 15 24 33 42 51 60, centre 33; 51 > 33, so discard 33 and the left side. Check 2: items 42 51 60, centre 51; 51 = 51, found. It takes 2 comparisons.
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.
Check 1: centre 33; 6 < 33, so discard 33 and the right side, leaving 6 15 24. Check 2: centre 15; 6 < 15, leaving 6. Check 3: centre 6; found. It takes 3 comparisons.
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.
Position
1
2
3
4
5
6
Item
2
8
14
20
26
32
The first centre item is 14 (the left of 14 and 20). Since 26 > 14, the items left are 20 26 32. The centre is 26, so it is found. It takes 2 comparisons.
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.
When the target is larger than the centre item, the left half and the centre are discarded, not the right half. Check 1: centre 40; 70 > 40, leaving 50 60 70. Check 2: centre 60; 70 > 60, leaving 70. Check 3: centre 70; found. It takes 3 comparisons.