Technologies K–10 · Years 9–10
Linear and binary search: counting comparisons on a million items
Computing Technology 7–10 (NSW, 2022); Digital Technologies: Processes and production skills, Producing and implementing (ACARA v9)
This site has no interactive model of its own. Where a step or a material names a Concept Studio model, simulation or tool, it has not been built; an external simulation a step names (for example PhET) is not part of this site.
The idea
Linear search checks items one by one, while binary search halves a sorted list each step, so for a million items the worst case falls from a million comparisons to 20.
What you need
- Computer with Python 3
- Spreadsheet for plotting
How to do it
- Make a sorted list of the whole numbers 1 to 1,000,000.
- Write linear_search and binary_search functions, each counting one comparison every time it checks the target against an item (for binary search, one three-way check per step: equal, smaller or larger).
- Search for the first item, the middle item, the last item and a missing value; record the counts.
- Repeat for lists of 10, 100, 1000, 10,000 and 100,000 items and plot worst-case comparisons against list size.
- Check the binary search against Python's bisect module.
- Explain when a single linear search is the better choice (an unsorted list searched once).
What you should see
For 1,000,000 items linear search needs up to 1,000,000 comparisons and 500,000.5 on average for items that are present; binary search never needs more than 20 (floor(log2 1,000,000) + 1 = 20). Each tenfold increase in size adds about 3.3 comparisons to binary search and multiplies linear search's by 10. Binary search needs the list sorted first. The learner knows it worked when the counts match these values and bisect finds the same positions.
What changes
This activity lists no variables to change, measure and keep the same.
Common misconceptions
Each of these ideas is wrong, and the activity is a chance to test it.
- Binary search works on any list (it needs sorted data).
- Doubling the list doubles binary search time (it adds one comparison).
- Faster computers make the algorithm choice irrelevant (the gap grows with n on any computer).
Safety card
Hazards
- None beyond normal computer use
Controls
- Not applicable
Note
No chemicals or heat.
Curriculum references
The NSW syllabus outcomes and Australian Curriculum v9 codes this activity supports. They are references, not a verified or complete curriculum alignment.
- Computing Technology 7–10 Syllabus (2022), NESA. Current elective syllabus. Code read from the outcomes page on 2026-09-22.CT5-OPL-01
- Australian Curriculum v9AC9TDI10P09
Sources
The pages the author read to write this activity.