GoalSearch sorted words, decide when an item is not in the list, and compare binary search with linear search.
New words
not found · the answer when there is no data left to check and the target has not appearedalphabetical order · words arranged by their letters, A to Zhalving · cutting the amount of data left to about half at every check
Explanation
A binary search can look for words as well as numbers, as long as the words are in alphabetical order. To compare two words, look at the first letter, and then the next one if the first letters match. A search also has to cope with a target that is not there. The search keeps discarding data, and at last there is nothing left. Then you report not found. You must not stop early: not found is only certain when no data is left. Binary search is quick because every comparison removes about half the data. A list of 1000 sorted items needs at most 10 comparisons, while a linear search might need 1000. But a binary search on unsorted data can give a wrong answer, so use a linear search when the data is not in order.
Items in the list
Most checks, linear search
Most checks, binary search
8
8
4
100
100
7
1000
1000
10
Worked examples
Check
Items still in play
Centre item
Compare
Decision
1
ant bee cat dove eel fox goat hen
dove
fox > dove
discard dove and everything to its left
2
eel fox goat hen
fox
fox = fox
found
A word that is in the list. The sorted words are ant, bee, cat, dove, eel, fox, goat and hen, and the target is fox. The first centre is dove, because there are eight items and the left middle one is the fourth. fox comes after dove, so the left half goes. Then eel, fox, goat and hen are left, and the centre is fox. It is found after 2 comparisons.
Check
Items still in play
Centre item
Compare
Decision
1
ant bee cat dove eel fox goat hen
dove
dog < dove
discard dove and everything to its right
2
ant bee cat
bee
dog > bee
discard bee and everything to its left
3
cat
cat
dog > cat
discard cat and everything to its left
(nothing left)
not found
A word that is not in the list. The same words, but the target is dog. The centre is dove, and dog comes before dove (g comes before v), so the right half goes. The words ant, bee and cat are left. The centre is bee, and dog comes after bee, so one word is left: cat. dog comes after cat, so nothing is left. The result is not found, after 3 comparisons.
Check
Items still in play
Centre item
Compare
Decision
1
5 9 14 100 23
14
23 > 14
discard 14 and everything to its left
2
100 23
100
23 < 100
discard 100 and everything to its right
(nothing left)
not found (wrong!)
Unsorted data gives a wrong answer. The list 5, 9, 14, 100, 23 is not in order, and the target is 23, which is in the list. The centre is 14, and 23 is larger, so the left part is discarded. Then 100 and 23 are left. The centre (left) is 100, and 23 is smaller, so the right is discarded. Nothing is left, so the search says not found. That is wrong, because 23 is there.
Class activity
Class register (no computer). Write these names in alphabetical order on a long strip: Aisha, Ben, Chen, Diego, Eli, Fatima, Hugo, Ivy, Jin, Kofi, Lara, Mila, Omar, Rosa, Sven. Choose a target name and find it twice. First do a linear search from the left, and count the names you check. Then do a binary search: take the left middle name each time and cover the half you discard. Count again. Try one name that is not on the strip.
Practice
1
Use a binary search for lemon in the sorted fruit list. Always take the left of two middle items. Write the centre item at each check and count the comparisons.
Position
1
2
3
4
5
6
7
Fruit
apple
fig
grape
kiwi
lemon
mango
peach
Check 1: items apple … peach (7 items), centre kiwi; lemon comes after kiwi, so the left part goes. Check 2: lemon mango peach, centre mango; lemon comes before mango, so the right part goes. Check 3: lemon; found. It takes 3 comparisons.
2
Use the same fruit list to look for date. What is the result, and how many comparisons are made?
Check 1: centre kiwi; date comes before kiwi, so the right part goes, leaving apple fig grape. Check 2: centre fig; date comes before fig, leaving apple. Check 3: apple; date comes after apple and nothing is left. The result is not found, after 3 comparisons.
3
A learner uses a binary search for 9 in the list 8, 3, 12, 1, 9. The search says not found, but 9 is in the list. Explain what went wrong and how to fix it.
Position
1
2
3
4
5
Item
8
3
12
1
9
The list is not sorted, so the discards are wrong. The centre 12 is larger than 9, so the right half is discarded, but 9 was in the discarded part. To fix it, sort the list first: 1, 3, 8, 9, 12. Then the search finds 9. (Or use a linear search, which does not need sorted data.)
4
A club has a sorted list of 1000 members. At most how many names could a linear search check? At most how many comparisons would a binary search make? Give one reason why you might still choose a linear search for a short list in no particular order.
A linear search could check up to 1000 names. A binary search needs at most 10 comparisons, because each comparison throws away about half of the names. For a short list in no particular order, a linear search is the better choice because it needs no sorting, and with only a few items the time saved by a binary search is tiny.