Unit 5 · Data and algorithms
Why binary search needs a sorted list
Binary search checks the middle and throws away the half that cannot hold the target. That only works if the list is sorted by the thing you are looking for. On a shuffled list, the middle tells you nothing.
The mix-up
What people often think
“Binary search works on any list.”
What the tutor says
Binary search trusts the order. On shuffled cards the middle tells you nothing about which side the target is on.
If the cards are shuffled, could a bigger number be hiding on the left?
How it works
In a list sorted small to large, if the middle is too big, the target must be on the left. On a shuffled list a bigger number could be hiding on either side, so binary search can skip straight past the target.
“Sorted” must mean sorted by the search key. Photos sorted by date say nothing about file size. When the list is not sorted that way, a linear search, checking each item in turn, is the correct choice.
Close cousins of this mix-up
The tutor watches for these in the same lesson.
“If the list is sorted at all, binary search works.”
It must be sorted by what you are looking for. Photos sorted by date say nothing about file size.
“Binary search is always faster, so use it everywhere.”
Speed only matters if the answer is right. Without the right order, binary search can skip straight past the target.
“If the middle is too big, look to its right.”
In a list sorted small to large, bigger numbers sit on the right. If the middle is too big, the target is on the left.
Practise it with a tutor watching
Search
Write a linear search and explain when binary search is allowed and why it wins.
Free with an account. The first two units need no account.