C37 · Topic 3.11 · 40 minutes · AAP-2.P
Halve an ordered search space
By the end you can:
- Trace every candidate interval using AP list positions.
- Explain why ordering justifies discarding a half.
- Recognise when the candidate interval becomes empty.
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
Binary search compares a target with the middle element of a sorted list. If they differ, ordering rules out one entire half. Repeat on the remaining interval. It is not valid to discard a half of an unordered list on that basis.
AP list positions begin at 1. In this investigation mid is the floor of (low + high) / 2. An unsuccessful search ends when low > high; never read a list position after the interval becomes empty.
Worked example
Find 25 in [4, 9, 13, 18, 25, 31, 42].
low ← 1
high ← LENGTH(values)
REPEAT UNTIL (low > high)
{
mid ← FLOOR((low + high) / 2)
IF (values[mid] = target) { RETURN(mid) }
IF (values[mid] < target) { low ← mid + 1 }
ELSE { high ← mid - 1 }
}
RETURN(0)- Positions 1…7: mid 4 contains 18. Discard positions 1…4 because all are below 25.
- Positions 5…7: mid 6 contains 31. Discard positions 6…7.
- Position 5 contains 25; return 5. The sentinel 0 would mean absent, not a valid AP list position.
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 works on any list because it checks the middle.
The discarded half is safe only when the list is sorted under the comparison rule.
Guided practice
Trace a search for 9 in the same list. Record low, high, mid and the compared value on each step.
Work with a partner. Make a prediction, compare your reasoning, then identify the rule that supports your answer.
Independent transfer
Trace a search for 26. Explain how the interval becomes empty rather than reading beyond the list.
Exit check
Why is sorting a prerequisite rather than just a cosmetic improvement?
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.