Linear search
Look through a list one item at a time, and count the steps.
Planned. This module is part of the plan and is not written yet.
Why it matters
Finding one learner's exercise book in an unsorted pile means checking one book at a time. In the worst case you check every book.
Draft outline · in review- For
- Level 9–11 · JSS 3 (BECE) to SSS 2
- Inside
- 4 lessons and a test · about 60 minutes
- Topic
- Searching and sorting · core, 2 of 4
Inside the module.
4 lessons in order, about 60 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: One item at a time
Linear search: start at the front and check each item in turn.
Explain10 min, from minute 0
Lesson 2: Searching in Python
Write a linear search that returns the position, or -1 if the item is not there.
Worked example15 min, from minute 10
Lesson 3: Write linear_search
Search lists of names and numbers, and test the not-found case.
Practice20 min, from minute 25
Lesson 4: Counting steps
Count comparisons for best, average and worst cases as the list grows.
Investigate15 min, from minute 45
End-of-module test
Write a linear search in Python and count the steps it takes in the worst case.
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 60 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 list holds 200 names in no particular order. In the worst case, how many names does a linear search check?
Particulars
Where it sits
Coding · Algorithms & data structures · Searching and sorting
What a learner can do after it
- Search a list item by item.
- Count the steps a linear search takes in the worst case.
Level
Level 9–11 · JSS 3 (BECE) to SSS 2
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
2 of 4 · Core
Time
About 60 minutes
Alignments
- Aligned to GCSEpartial · in reviewGCSE Computer Science: searching algorithms (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-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 · the destination Needs Parameters and return values (required), Lists (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.