Binary search is an efficient search algorithm that uses a divide-and-conquer strategy.
Here is an ordered list of data values with their corresponding index positions:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Value | 5 | 8 | 12 | 15 | 17 | 19 | 22 | 24 | 27 | 30 |
A binary search is executed to find whether the number 14 is in the list.
The midpoint is calculated by adding the low index to the high index and using integer division by 2 (e.g., (low + high) // 2).
Complete the table below to show the values of the low index, high index, and midpoint for each pass of the binary search algorithm until it terminates.
| Pass | Low Index | High Index | Midpoint |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 |
45 exam-style questions on Edexcel IGCSE Computer Science Algorithms. Each one has a worked solution and a mark scheme showing where the marks go.