| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Marks | 7 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Binary Search Execution |
| Difficulty | Moderate -0.8 This is a straightforward application of binary search requiring description of the algorithm and a simple logarithm calculation (log₂(1,000,000) ≈ 20). Part (a) tests basic understanding of the strategy, part (b) requires knowing that maximum searches = ⌈log₂(n)⌉, which is standard D1 content with minimal problem-solving demand. |
| Spec | 7.03a Algorithm definition: input, output, deterministic, finite7.03d Order of algorithm: dominant term and scaling run-times |
| Answer | Marks | Guidance |
|---|---|---|
| (a) e.g. choose middle name, latter if middle pair; interrogate, giving answer or list of about half the previous list; repeat until celebrity found | B4 | |
| (b) With list of 1 name, need 1 interrogation. With list of 2 names, need a maximum of 2 interrogations. With list of 4 names, need a maximum of 3 interrogations etc. With list of \(2^n\) names, need a maximum of \((n+1)\) interrogations. \(2^{20} = 1,048,576\) so with 1 million need a maximum of 21 interrogations. (accept 20) | M2 A1 | (7) |
**(a)** e.g. choose middle name, latter if middle pair; interrogate, giving answer or list of about half the previous list; repeat until celebrity found | B4 |
**(b)** With list of 1 name, need 1 interrogation. With list of 2 names, need a maximum of 2 interrogations. With list of 4 names, need a maximum of 3 interrogations etc. With list of $2^n$ names, need a maximum of $(n+1)$ interrogations. $2^{20} = 1,048,576$ so with 1 million need a maximum of 21 interrogations. (accept 20) | M2 A1 | (7) |
---2. In a television gameshow the names of 100 celebrities are listed in alphabetical order. A name is chosen at random from the list and a contestant has to guess which celebrity has been chosen. If the contestant is not correct, the host indicates whether the chosen name comes before or after the contestant's answer in the list and the contestant makes another guess.
Each contestant knows all the names on the list and has to find the chosen name in as few guesses as possible.
\begin{enumerate}[label=(\alph*)]
\item Describe a strategy which would enable the contestant to find the chosen name in as few guesses as possible.
\item A large database with up to one million ordered entries is to be interrogated in the same way using appropriate software. Find the maximum number of interrogations that would be required for the software to find a particular entry and explain your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 Q2 [7]}}