You're looking for a name in a printed phone book with 1,000 sorted pages. Which strategy finds it in far fewer steps: checking every page one by one from the start, or repeatedly opening to the middle of the remaining pages and deciding which half to search next?
- Opening the middle page each time and eliminating half the remaining pages at every step, because the pages are already sorted alphabetically, quickly narrows down where the name must be
- Checking every page one by one, because binary search only saves time when you already know exactly which page the name is on
- Opening the middle page each time, because splitting a list in half always cuts the work equally, whether or not the pages are sorted
- Checking every page one by one, because with only 1,000 pages, one-by-one checking and middle-splitting take roughly the same number of steps overall
Why A? And why not the others?
Correct answer: A. Opening the middle page each time and eliminating half the remaining pages at every step, because the pages are already sorted alphabetically, quickly narrows down where the name must be
This is binary search: because the pages are already sorted alphabetically, comparing the wanted name to the name on the middle page tells you immediately which half of the remaining pages the name must be in, so that whole half can be thrown away in one step; repeating this halves the remaining pages each time, so a 1,000-page book needs only about ten comparisons rather than up to a thousand. The option describing one-by-one checking as needing to already know the exact page is backwards; that requirement describes nothing about linear search, and binary search actually works precisely because you do not know the page in advance, narrowing it down step by step instead. The option claiming halving works the same whether or not pages are sorted is wrong because without a sorted order there is no way to know which half contains the name, so the middle-page trick would not reliably eliminate the right half at all. The option claiming both methods take a similar number of steps is wrong by a huge margin: one-by-one checking can need up to 1,000 steps in the worst case, while halving needs only around ten, an enormous practical difference at this scale.
Source: BBC Bitesize GCSE Computer Science: Searching algorithms