Linear or binary search?
Search 16 numbers two ways: one by one, and by halving the list at each step. Compare the comparisons each needs, then run binary search on a list that is not sorted and see it miss a number that is there.
Core concept
Binary search compares the target with the middle of a sorted list and throws away the half it cannot be in, so 16 items need at most 5 comparisons instead of 16; it only works on sorted input
Topic: Algorithms
Think of finding a word in a dictionary. You do not read every page: you open it in the middle, see that your word comes later, and look only in the second half, then halve again. That is binary: Counting with only two digits, 0 and 1. Computers store everything this way. All key words search. It keeps a window from low to high, looks at the middle item (mid), and if the target is bigger it moves low to mid + 1; if smaller, it moves high to mid − 1. Each comparison throws away half of what is left, so 16 items need at most 5 comparisons, and a million need only about 20. The catch: the list must be sorted, or the half it throws away may hold the target. Linear search needs no order but may check every item.
What you will learn
- Trace binary search with low, high and mid.
- Compare the comparisons of linear and binary search on the same target.
- Explain why binary search needs a sorted list.
- Estimate the most comparisons binary search needs for a list of a given size.
Before you start
- Know linear search and list indexes.
Materials
- A notebook to record the comparisons
Equipment
- None
Procedure
- Run linear search for 60 in the sorted list and count the comparisons.
- Switch to binary search for the same target and compare.
- Run binary search on the mixed (unsorted) list and see what happens.
- Answer the practice challenges.