C38 · Topic 3.11 · 40 minutes · AAP-2.P
Choose a search strategy and test its boundaries
By the end you can:
- Choose linear or binary search for a stated data setting.
- Test empty, singleton, absent and duplicate cases.
- Compare a particular run with worst-case growth.
Before this lesson: topics 3.2, 3.6, 3.8.
- Sorted
- Ordered according to the same comparison rule used by the search.
- Search interval
- The inclusive range of positions that may still contain the target.
Understand
A linear search can examine an unsorted list, comparing elements in turn. A binary search typically needs far fewer comparisons on a large sorted list, but sorting has a cost. For a single search of unsorted data, sorting first may cost more than a traversal.
Distinguish worst case from a particular run. A target at the first position can make linear search faster on that run; that does not establish better worst-case growth. Duplicates do not invalidate binary search, but this version returns some matching position, not necessarily the first.
Worked example
Compare worst-case unsuccessful searches in sorted lists.
- 7 entries: linear may compare 7; binary at most 3.
- 15 entries: linear may compare 15; binary at most 4.
- 31 entries: linear may compare 31; binary at most 5. Doubling approximately adds one binary-search comparison.
Explore each concept
Choose a concept, change its inputs and follow the explanation. Each example models the stated rule or scenario; completing it is practice rather than evidence of mastery.
- Unsorted versus sorted data
- First match versus some match
- Measured comparisons versus worst case
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Values (0–100; max 8)7,2,7,1Waiting
- Target (0–100)7Waiting
- AlgorithmlinearWaiting
Ready to explore: Choose linear search or binary search
Why: Change an input, predict the first effect, then advance one step.
Try this: Change one input or choose another listed case. Predict the effect, reset and compare the states and governing rule.
Step through and experiment
Change it · step through · explain
Change an input, predict what will happen, then advance one step. Read why the state changes, reset and experiment. This fixed teaching model does not save progress or award XP.
Ready · Make a prediction
- Input 14,9,13,18,25,31,42Waiting
- Input 226Waiting
Ready to experiment
Why: Predict the first change, then advance one step.
Try this: Try the first and last items, a missing value, duplicates and an empty list.
Check a misconception
Claim: Binary search must return the first occurrence of a repeated value.
A middle-element match can stop immediately; finding the first occurrence needs a modified algorithm.
Guided practice
Give tests for empty, singleton present and singleton absent lists, stating the returned positions.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
A sensor app receives one unsorted reading list and asks once whether 17 occurs. Recommend a method and justify the data prerequisite and preprocessing cost.
Exit check
For an already sorted list of 63 entries, what is the maximum number of middle-element comparisons in this version?
Write your reasoning before comparing with a classmate. If your teacher assigned this task, submit it through My classes to save your work and receive feedback.
Check yourself
Your practice so far
Check an answer to see its rationale.