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
3

Not in the list

Computing 9: Topic 1.7, pp. 128–134
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 listMost checks, linear searchMost checks, binary search
884
1001007
1000100010
Worked examples
CheckItems still in playCentre itemCompareDecision
1ant bee cat dove eel fox goat hendovefox > dovediscard dove and everything to its left
2eel fox goat henfoxfox = foxfound
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.
CheckItems still in playCentre itemCompareDecision
1ant bee cat dove eel fox goat hendovedog < dovediscard dove and everything to its right
2ant bee catbeedog > beediscard bee and everything to its left
3catcatdog > catdiscard 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.
CheckItems still in playCentre itemCompareDecision
15 9 14 100 231423 > 14discard 14 and everything to its left
2100 2310023 < 100discard 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.
Position1234567
Fruitapplefiggrapekiwilemonmangopeach
2
Use the same fruit list to look for date. What is the result, and how many comparisons are made?
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.
Position12345
Item831219
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.