ITPEC FE Subject B April 2025 Question 7

Topic: Array Manipulation

From the answer group below, select the correct answer to be inserted into blank in the description. Here, the array index starts at 1.

The function binarySearch receives four arguments: the first argument is an array specified with the argument arr (the number of elements ≥ 1), the second argument is the value specified with the argument target, the third argument is the lower bound low of the array, and the fourth argument is the upper bound high of the array. The array arr has no duplicate elements and is sorted in ascending order. If arr has an element with the same value as target, this function returns the index of that element, and -1 otherwise.

When the function binarySearch is called as binarySearch({1, 2, 3, 4, 5, 6}, 5, 1, 6), the number of times the string “call” is output is blank.

[Program]
○ integer: binarySearch(integer []: arr, integer: target,
integer: low, integer: high)
integer: mid
if (low > high)
return -1
endif
mid ← integer part of ((low + high) ÷ 2)
if (arr[mid] > target)
output "call"
return binarySearch(arr, target, low, mid - 1)
elseif (arr[mid] < target)
output "call"
return binarySearch(arr, target, mid + 1, high)
else
return mid
endif

Answer group

Explanation

1 — only the first probe misses; the second lands on 5 and returns without printing.

"call" is printed just before each recursive call, in the two branches where arr[mid] is not the target. The branch that finds the target returns mid and prints nothing.

Calllowhighmidarr[mid]Result
116333 < 5: output "call", search 4 to 6
24655equal: return 5, no output

Here mid is (1 + 6) ÷ 2 = 3.5, integer part 3, then (4 + 6) ÷ 2 = 5. "call" appears once.

Answer (b)

Why not others:

  • •(a) 0 — would need a hit at the first probe, but arr[3] is 3, not 5.
  • •(c) 2 — counts the second call as well, but the branch that finds the target outputs nothing; 2 is the count for target 6.
  • •(d) 3 — the most a 6-element array can produce, reached only when the target is absent (for example 7).
  • •(e) 4 — the misses a linear scan would make before reaching index 5; binary search halves the range instead.
  • •(f) 5 — the return value, the index of 5, not the number of outputs.
  • •(g) 6 — the number of elements; more than 3 calls is impossible when each probe halves a range of 6.

Key rule: When counting outputs in a recursive search, check which branches print; the base case that finds the target usually does not.

Array Manipulation · AI-written, may contain errors

Practice this exam

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.