Find an item without checking everything
When does dividing the search space save work?
Entering midway? Revisit Build a price calculation tool for the preceding worked example, or start here and use the explanation below.
Start with a concrete question
Search an original synthetic sorted inventory of consecutive IDs. Each inspected item counts as one unit of algorithmic work; this is not elapsed computer time.
Try the initial inputs, then write a prediction before changing one setting. All calculations run locally on your CPU.
What do you expect?
Predict a target for which a linear scan beats binary search.
Change one thing. Inspect what happens.
- Search for ID 13 among 16 items with both methods. Inspect each decision.
- Search for ID 1. Find the counterexample to “binary search always uses fewer inspections”.
- Set size to 8 and target to 20. Explain how each method proves absence.
Your settingsMechanism
Calculation belowEvidence
Compare outcomes
Compare the current results
Every bar starts at zero and uses the same numeric scale in this chart. The upper bound automatically adjusts to the largest current value (at least 1), so compare the numbers when changing inputs. Units and quantities come from each label; different kinds of quantity are not interchangeable. Displayed values are rounded to at most six significant digits.Follow the calculation
- Sorted synthetic inventory IDs: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16. Search for 13.
- Indices 0–15; middle 7 holds 8. Keep the higher half.
- Indices 8–15; middle 11 holds 12. Keep the higher half.
- Indices 12–15; middle 13 holds 14. Keep the lower half.
- Indices 12–12; middle 12 holds 13. Match.
A match was found. Compare the same target with both methods; the first item can favor a scan.
Captures keep your inputs, prediction and observation. Results are recalculated from those inputs. Resetting inputs keeps your captures and challenge history.
Explain the mechanism
Find an item without checking everything
Search an original synthetic sorted inventory of consecutive IDs. Each inspected item counts as one unit of algorithmic work; this is not elapsed computer time.
Before you change anything
Predict a target for which a linear scan beats binary search.
Follow the mechanism
A linear scan checks items in order. Binary search checks the middle and discards the half that cannot contain the target.
With IDs 1–16, binary search for 13 inspects 8, 12, 14 and 13: four items. A scan inspects thirteen.
Discarding half is valid because the inventory is sorted. Without that invariant, binary search can miss an existing item.
Calculate it yourself
Middle index = floor((low + high)/2); discard indices below or above it according to the comparison.
Try a counterexample
Search for ID 13 among 16 items with both methods. Inspect each decision.
Search for ID 1. Find the counterexample to “binary search always uses fewer inspections”.
Set size to 8 and target to 20. Explain how each method proves absence.
What this model leaves out
Sorting and data-access costs are excluded. These are comparisons, not timing benchmarks.
No learner code executes here. This activity teaches trace reasoning; independent implementation needs a separate program and tests.
Take it further
High school: Play a number-guessing game and record the remaining interval after every guess.
College: Implement both methods, test absent and duplicate keys, and prove termination.
Working professionals: Compare indexed lookup with scanning, including index construction and update costs.
Try a fresh case
Binary search uses the lower middle on IDs 1–8. How many items does it inspect to find ID 7?
This is a public practice check. Retries support learning; matching a number does not certify independent proficiency.
Take the investigation further
Choose any extension. These are project prompts for you to carry out; they are not automatically assessed.
School investigation
Play a number-guessing game and record the remaining interval after every guess.
College investigation
Implement both methods, test absent and duplicate keys, and prove termination.
Workplace investigation
Compare indexed lookup with scanning, including index construction and update costs.
Keep the evidence, choose your next step
Completion records your own decision that you have worked through this investigation. Practice checks and independent project evidence are separate.