Linear search vs. binary search – counting comparisons
Computer ScienceAlgorithms & Problem SolvingAges 12–13
Use it with your class: students open it from a link or a QR code, with no account needed.
Next in Algorithms & Problem Solving
The same array and the same target value run through linear search (scanning from the start) and binary search (halving the range on a sorted array) side by side. Students click Step or Play to see the cell being compared, the range being ruled out, and the comparison count for each algorithm; clicking a cell changes the target value, and turning sorting off shows why binary search stops working.
Lesson: Linear search algorithm; binary search algorithm
What it shows
Linear search checks the elements one by one from the start, so in the worst case it needs as many comparisons as there are elements. Binary search compares the target with the middle element of a sorted array and discards the half that cannot contain it, so it needs at most about log₂n + 1 comparisons, just five for sixteen elements. Counting comparisons for both algorithms on the same array shows why binary search wins on long lists, and why it depends completely on the data being sorted first.
How to use
Set Algorithm to Both (compare), choose the Number of elements and click Step to follow each comparison: the highlighted cell, the low, mid and high markers and the part of the array ruled out. Click a cell to change the target, or use Play for a full run. Try a target near the start of the array, then turn off Array sorted in ascending order to see why binary search can no longer be used.
Parameters you can change
- Number of elements 5–20
- Target value (0 = pick randomly from the array) 0–99
- Algorithm Both (compare), Linear search, Binary search
- Array sorted in ascending order
- Run speed 1–5 steps/s
Questions to explore
- What is the largest number of comparisons binary search needs to find a value in an array of 16 elements?
- For which target values does linear search need fewer comparisons than binary search?
- Why can binary search no longer be used once the array is not sorted?
