IPA FE Subject B sample Question 13

Topic: Array Manipulation

A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問13, translated into English. ITPEC is based on the same exams.

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 search returns the index of the element if the value specified by the argument target is contained in the array specified by the argument data, and returns −1 if it is not contained. data is sorted in ascending order, and there are no duplicate values.
The function search has a defect. For example, in the case of data where blank, an infinite loop occurs.

[Program]
○ integer: search(integer []: data, integer: target)
integer: low, high, middle
low ← 1
high ← the number of elements in data
while (low ≤ high)
middle ← the quotient of (low + high) ÷ 2
if (data[middle] < target)
low ← middle
elseif (data[middle] > target)
high ← middle
else
return middle
endif
endwhile
return -1

Answer group

Explanation

Two elements, target equal to the last one — the search keeps middle inside the range (low ← middle), so the range can stop shrinking.

Take data = {3, 7} and target = 7. Then low = 1, high = 2, and middle = the quotient of 3 ÷ 2 = 1. Since data[1] = 3 < 7, low ← middle sets low to 1, its old value. Nothing has changed, so every pass computes middle = 1 again and low ≤ high stays true forever.

In general, once high = low + 1, the quotient gives middle = low, and a target above data[middle] leaves low where it is. A correct binary search moves past the middle: low ← middle + 1 and high ← middle - 1. Running the program for each option confirms that only this case loops.

Answer (c)

Why not others:

  • •(a) — low = high = 1, so middle = 1 holds target and the function returns 1 on the first pass
  • •(b) — middle = 1 is the first element, which equals target: it returns 1 on the first pass
  • •(d) — a stored −1 has nothing to do with the loop, which depends only on where target sits: search({-1, 4, 9}, -1) returns 1

Key rule: In a binary search, the new bounds must exclude the midpoint (middle + 1, middle - 1); otherwise two neighbouring bounds can leave the range unchanged for ever.

Array Manipulation · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.