ITPEC FE Subject B April 2025 Question 7
ITPEC FE Subject B April 2025 — Question 7 of 20
Binary Search call counting — trace a recursive binary search and count how many times "call" is printed.
Call binarySearch({1,2,3,4,5,6}, 5, 1, 6) with 1-based indexing:
| Call | low | high | mid | arr[mid] | vs target | Action |
|---|---|---|---|---|---|---|
| 1 | 1 | 6 | 3 | 3 | 3 < 5 | output "call", recurse(arr, 5, 4, 6) |
| 2 | 4 | 6 | 5 | 5 | 5 == 5 | return 5 (no output) |
"call" is printed only in the if (arr[mid] > target) or elseif (arr[mid] < target) branches — NOT in the else (match) branch. The target is found on the second call, so "call" is output 1 time.
Why not others:
- (a) 0 — would mean the target was found on the very first mid calculation, but mid=3 and target=5
- (c) 2 — would require three calls before finding; only two calls are made
- (d) 3 — too many; the array has only 6 elements, binary search converges fast
Key rule: "call" is printed on every recursive call except the one that finds the target (the else branch).
AI-generated — may contain errors
The original exam layout is preserved in the image so diagrams, formulas, tables, and code remain accurate.
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.