The table below shows the number of minutes that bicycle-share users kept a bicycle on Saturday. A programmer will use a linear search algorithm to find a r...
Question 1 Report
The table below shows the number of minutes that bicycle-share users kept a bicycle on Saturday. A programmer will use a linear search algorithm to find a requested booking number in the list. Fig. 1 represents the search: each diamond tests one item of data, and the program stops at the first correct match. The user types 407 into an input box. The list is not sorted, so binary search cannot be used without changing the data first.
| List position | Booking number | Minutes used |
|---|---|---|
| 1 | 325 | 14 |
| 2 | 407 | 31 |
| 3 | 198 | 8 |
| 4 | 512 | 27 |
(a) Identify the position at which the program finds booking number 407. [1]
(b) State the output displayed for this booking number. [1]
(c) Give two reasons why the algorithm may need to test more than one item of data. [2]
Answer Details
(a) The program finds booking number 407 at position 2. [1] A linear search begins at position 1, sees 325 is not a match, then compares the next item.
(b) The corresponding output is 31 minutes. [1] This is the minutes-used value in the same record as booking number 407.
(c) A linear search may test more than one item because:
- the required number may not be the first item in the list; [1]
- the list is unsorted, so the program must compare items in turn rather than discard half of the list. [1]
It could also need to inspect all items if the requested number is absent. For an unsorted list, do not assume a middle comparison can rule out either half.
Download The App On Google Playstore
Everything you need to excel in your exams
