Practice question · Multiple choice
You guess a number between 1 and 1000; after each guess you learn "higher" or "lower". A smart player needs at most 10 guesses. What strategy achieves this?
Hints
- What single guess guarantees you eliminate half the possibilities, whatever the answer?
- 1000 → 500 → 250 → … how many halvings until one candidate remains? (.)
Show the answer
C. Always guess the middle of the range
Why
Binary search: each middle guess halves the search space, so 1000 candidates fall in steps. The same idea finds words in dictionaries, entries in databases, and bugs in version history (git bisect), provided the data is sorted.
Practise Searching and sorting ideas
The app has 8 more questions on this lesson, and keeps your place in the course. Physics I is free to start.
More questions on Searching and sorting ideas
- Trace selection sort on the list [7, 2, 9, 1]. Order the states the list passes through.
- Classify each sort as O(n²) average or O(n log n) average.
- Binary search is far faster than linear search but is used less often in practice. Why is it used less often…
- Order the steps of merge sort on [3, 1, 4, 2].
- Binary search finds a name among 1,000 sorted entries in ~10 steps. Estimate the steps needed for…