F14 · Topic 3.11
Search interval detective
1. Predict first
For [4,9,13,18,25,31,42] and target 26, predict every middle value and the final result.
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.
2. Build your procedure
Write a search procedure using the inclusive low/high invariant. Add a separate linear-search procedure. Keep the input sorted for the binary comparison; do not execute student code in this tool.
Use AP CSP pseudocode, a language you know, or precise plain language. Your code is not executed here. Use the classroom assignment to save your response.
3. Check boundaries
| Input | Expected | Why this case |
|---|---|---|
| []; target 4 | Absent; 0 comparisons | No valid interval. |
| [4]; target 4 | Position 1; 1 comparison | Smallest successful list. |
| [4,9,13,18,25,31,42]; target 26 | Absent; middle values 18,31,25 | Target between neighbours. |
4. Explain and reflect
Why would replacing low ← mid + 1 with low ← mid risk nontermination?
Model limits: The tool rejects unsorted values rather than silently sorting. It traces one fixed search model, not arbitrary submitted code.