Time allowed: 40 minutes
| Centre number |
| | | |
|
Candidate number |
| | | |
| First name |
|
Last name |
INSTRUCTIONS
- Use black ink.
- Answer all the questions.
INFORMATION
- The total mark for this paper is 35.
- The marks for each question are shown in brackets [ ].
Turn over
Section A: Prerequisites & Definitions
1
(a) State the main condition that a list (array) must meet before a
Binary Search can be performed.
[1]
(b) Explain why a
Linear Search does not have this same condition.
[1]
2
Tick
one box in each row to identify whether the statement applies to a Linear Search or a Binary Search.
[3]
| Statement |
Linear Search |
Binary Search |
| It checks every item in the list one by one. |
|
|
| It calculates a midpoint to divide the list. |
|
|
| It is generally faster for very large, sorted lists. |
|
|
Section B: Performing Linear Searches
3
The following list of names is held in an array called
students:
Ali
Bea
Dan
Fay
Leo
Mia
Sam
Zoe
A Linear Search is performed to find the name "
Sam".
(a) State how many items will be checked before "Sam" is found.
[1]
(b) A Linear Search is performed to find the name "
Ben".
Explain what will happen during this search.
[2]
Turn over
Section C: Performing Binary Searches
4
The following list of numbers is stored in an array.
The list is sorted in ascending order.
Show the steps of a
Binary Search to find the value
19.
You must show the calculation for the midpoint at each step.
(Note: When calculating the midpoint, round down to the nearest integer).
[4]
Step 1: List range [0 to 8]. Midpoint = (0 + 8) / 2 = 4. Value at index 4 is 15.
15 < 19, so discard left half.
Step 2:
Step 3:
Result:
5
Using the same list as Question 4:
[2, 5, 9, 11, 15, 19, 22, 25, 30]
A Binary Search is performed to find the value
2.
Complete the trace table below to show the values of the variables
low,
high, and
mid at each stage.
[3]
| Stage |
low |
high |
mid |
Value at mid |
| 1 |
0 |
8 |
4 |
15 |
| 2 |
|
|
|
|
| 3 |
|
|
|
|
6
A student has written a Binary Search algorithm for the following list:
[10, 45, 2, 19, 88, 30]
Explain why the Binary Search algorithm will
fail to find the number 19 correctly in this specific list.
[2]
Turn over
Section D: Algorithms & Comparison
7
Complete the pseudocode for a
Linear Search algorithm by filling in the missing gaps.
[4]
target = input("Enter value to find")
found = False
index = 0
WHILE index < length(list) AND found == False
IF list[index] == ........................................ THEN
found = ........................................
print("Found at position " + index)
ELSE
index = ........................................ + 1
ENDIF
ENDWHILE
IF found == False THEN
print("........................................")
ENDIF
8
Write the steps for a
Binary Search algorithm in structured English (bullet points).
Your steps should describe the logic of checking the midpoint and splitting the list.
[5]
9
A library has a database of 1,000,000 books stored in order of ISBN.
Compare the efficiency of
Binary Search versus
Linear Search for finding a specific book in this database.
In your answer, consider the worst-case scenario for both algorithms.
[4]
10
A programmer has a list of 10 items. They claim that "Binary Search is always faster than Linear Search."
Explain why this statement is
incorrect by giving an example scenario where Linear Search would be faster or equal.
[2]
END OF QUESTION PAPER