Binary search
Halve a sorted list again and again to find something fast.
Planned. This module is part of the plan and is not written yet.
Why it matters
To find a word in a dictionary, you open it near the middle and ignore the half the word can't be in. Binary search does the same to a sorted list.
Draft outline · in review- For
- Level 10–12 · SSS 1 to SSS 3 (WASSCE)
- Inside
- 5 lessons and a test · about 75 minutes
- Topic
- Searching and sorting · extension, 3 of 4
Inside the module.
5 lessons in order, about 75 minutes in all, then a short test. Learners go at their own pace; the minutes are a guide, not a timetable.
Draft outline · in review
Lesson 1: Halving
Guess the middle, then throw away the half that can't hold the answer.
Explain10 min, from minute 0
Lesson 2: Why sorted?
See binary search fail on an unsorted list.
Discussion10 min, from minute 10
Lesson 3: Binary search in Python
Code it with low, high and mid, and trace each step.
Worked example20 min, from minute 20
Lesson 4: Implement and test
Write your own and test it on the first, last and missing items.
Practice20 min, from minute 40
Lesson 5: Steps as lists grow
Compare the steps for linear and binary search on lists of 10 to 1,000,000 items.
Investigate15 min, from minute 60
End-of-module test
Explain why binary search needs sorted data, implement it in Python and compare its steps with linear search.
Mastered at 85% or more. Retake it until you pass; nothing is lost, and each try gives feedback.
Already know it? A Challenge Test (planned) clears the whole module: 90% overall, no objective below 75%.
Last stageafter about 75 min
Practicalities
Draft outline · in reviewBuilt to run offline
Planned to run on the Lantern's own computer, with no internet needed.
Languages
Planned first in English; every module aims to reach all of the Lantern's languages.
Try a question.
One question from the module, as a learner would meet it. Have a go, then open the worked solution a step at a time.
Draft outline · in review
A sorted list has 1,000 items. What is the most comparisons a binary search needs, and how does that compare with a linear search?
Work it out on paper first, then show the answer and mark it yourself.
Particulars
Where it sits
Coding · Algorithms & data structures · Searching and sorting
What a learner can do after it
- Explain why binary search needs a sorted list.
- Implement binary search in Python.
- Compare its steps with linear search as the list grows.
Needs first
Level
Level 10–12 · SSS 1 to SSS 3 (WASSCE)
Level mappings are approximate. A qualified teacher or lecturer in each country must check them before they appear in the app.
Difficulty for its level
3 of 4 · Extension
Time
About 75 minutes
Alignments
- Aligned to GCSEpartial · in reviewGCSE Computer Science: searching algorithms (descriptive ref)
- Aligned to APpartial · in reviewAP Computer Science A: searching (descriptive ref)
Alignment in review until a qualified teacher or lecturer checks it. No exam body, university or vendor endorses us; learners still sit the real exam.
Challenge Test
Planned: a Challenge Test to prove you know it and skip it. Pass at 90% overall, with no objective below 75%.
University courses it previews
Computer Science, Software Engineering
On these pathways
The route here.
Everything this module builds on, drawn as a route from its foundations. Solid lanes must be mastered first, or cleared by a Challenge Test; dashed lanes are suggestions that never lock anything.
- CO-BLK-SEQ-01 Instructions in order, Level 1–4, Coding. Planned.
- CO-BLK-SEQ-01Instructions in orderCoding · Primary 1 to Primary 4 (Level 1–4) · Planned
- CO-BLK-LOP-01 Repeat blocks, Level 3–5, Coding. Sample lesson in the demo.
- CO-BLK-LOP-01Repeat blocksCoding · Primary 3 to Primary 5 (Level 3–5) · Sample lesson in the demo Needs Instructions in order (required).Try the sample lesson: Repeat blocks
- DS-CMP-TYP-01 The home row, Level 3–6, Digital skills. Planned.
- DS-CMP-TYP-01The home rowDigital skills · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
- CO-BLK-CND-01 If this, then that, Level 3–6, Coding. Planned.
- CO-BLK-CND-01If this, then thatCoding · Primary 3 to Primary 6 (Level 3–6) · Planned · recommended
- CO-BLK-LOP-02 Patterns with loops, Level 4–6, Coding. Planned.
- CO-BLK-LOP-02Patterns with loopsCoding · Primary 4 to Primary 6 (Level 4–6) · Planned Needs Repeat blocks (required).
- MA-ARI-ORD-01 Order of operations, Level 5–6, Maths. Planned.
- MA-ARI-ORD-01Order of operationsMaths · Primary 5 to Primary 6 (Level 5–6) · Planned · recommended
- CO-BLK-LOP-03 Loops inside loops, Level 5–7, Coding. Planned.
- CO-BLK-LOP-03Loops inside loopsCoding · Primary 5 to JSS 1 (Level 5–7) · Planned · recommended
- CO-PRG-PYB-01 Your first Python program, Level 7–9, Coding. Planned.
- CO-PRG-PYB-01Your first Python programCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Patterns with loops (required), The home row (recommended).
- CO-PRG-PYB-02VariablesCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Sample lesson in the demo Needs Your first Python program (required).Try the sample lesson: Variables
- CO-PRG-PYB-03Numbers and calculationsCoding · JSS 1 to JSS 3 (BECE) (Level 7–9) · Planned Needs Variables (required), Order of operations (recommended).
- MA-ALG-FRM-01Substituting into formulaeMaths · JSS 1 to JSS 2 (Level 7–8) · Planned · recommended
- CO-PRG-PYB-05Decisions with ifCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Numbers and calculations (required), If this, then that (recommended).
- CO-PRG-PYB-06Loops in PythonCoding · JSS 2 to SSS 1 (Level 8–10) · Planned Needs Decisions with if (required), Loops inside loops (recommended).
- CO-PRG-PYF-01Defining functionsCoding · JSS 2 to SSS 2 (Level 8–11) · Planned Needs Loops in Python (required).
- CO-PRG-PYF-02Parameters and return valuesCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Defining functions (required), Substituting into formulae (recommended).
- CO-ALG-SRT-01Linear searchCoding · JSS 3 (BECE) to SSS 2 (Level 9–11) · Planned Needs Parameters and return values (required), Lists (required).
- CO-ALG-SRT-02Binary searchCoding · SSS 1 to SSS 3 (WASSCE) (Level 10–12) · Planned · the destination Needs Linear search (required).
Help light the room where this is learned.
Every route on this map starts in a classroom with 24 stations, a tutor that works offline and a facilitator upstairs. Four are planned and waiting for light.