A program searches sorted numerical data using a binary search. The figure shows the list before the search begins. Positions start at 0, and the target num...
Question 1 Report
A program searches sorted numerical data using a binary search. The figure shows the list before the search begins. Positions start at 0, and the target number is 42.
low ← [A]
high ← [B]
found ← FALSE
WHILE low ≤ high AND found = FALSE
middle ← INTEGER((low + high) / 2)
IF data[middle] = target THEN
found ← TRUE
ELSE IF target > data[middle] THEN
low ← middle + 1
ELSE
high ← middle - 1
ENDIF
ENDWHILE| comparison | low | high | middle | data[middle] | action |
|---|---|---|---|---|---|
| 1 | 0 | 7 | 3 | 27 | low ← 4 |
| 2 | 4 | 7 | 5 | 56 | [C] |
| 3 | 4 | [D] | 4 | 42 | found ← TRUE |
(a) State one property the data must have for binary search to work. [1]
(b) Complete [A] and [B]. [2]
(c) Give the value of middle during the first comparison. [2]
(d) Convert this instruction into pseudocode: “When the target is greater than the middle figure, search the upper half.” [2]
(e) Complete [C] and [D] in the trace table. [2]
(f) Explain why binary search is usually faster than linear search for a large list. [2]
(g) Give the values of low and high immediately after comparison 2. [2]
(h) State the position that the program should display when the target is found. [2]
Answer Details
(a) Binary search requires the data to be sorted, for example in ascending order [1]. This is what allows one half to be discarded after each comparison.
(b) Initially, low ← 0 and high ← 7 [2], the first and final valid list positions.
(c) \[\text{middle}=\operatorname{INTEGER}\left(\frac{0+7}{2}\right)=3\] Therefore middle is 3 [2].
(d) Searching the upper half is low ← middle + 1 [2].
(e) Since 42 is less than 56, comparison 2 sets high ← 4. Thus the next high value is 4 [2].
(f) Each binary-search comparison removes approximately half the remaining items. A linear search may compare every item, so binary search needs far fewer comparisons for a large sorted list [2].
(g) Immediately after comparison 2, low = 4 and high = 4 [2].
(h) The target 42 is at position 4 [2].
Download The App On Google Playstore
Everything you need to excel in your exams
