サンプル問題セット(2022年12月公開) 科目B 問13
次の記述中の[ ]に入れる正しい答えを,解答群の中から選べ。ここで,配列の要素番号は 1 から始まる。
関数 search は,引数 data で指定された配列に,引数 target で指定された値が含まれていればその要素番号を返し,含まれていなければ[ ]-1 を返す。data は昇順に整列されており,値に重複はない。
関数 search には不具合がある。例えば,data の[ ]場合は,無限ループになる。
○整数型: search(整数型の配列: data, 整数型: target)
整数型: low, high, middle
low ← 1
high ← dataの要素数
while (low ≦ high)
middle ← (low + high) ÷ 2 の商
if (data[middle] < target)
low ← middle
elseif (data[middle] > target)
high ← middle
else
return middle
endif
endwhile
return -1
| a | |
|---|---|
| ア | {5}, 5 |
| イ | {3, 8}, 3 |
| ウ | {3, 8}, 8 |
| エ | {-1, 3, 8}, -1 |
出典:基本情報技術者試験 科目B試験 サンプル問題セット(2022年12月公開) 問13
正解と解説を見る
正解:ウ
ポイント:2分探索で low ← middle(+1 しない)にすると、範囲が縮まらず無限ループになる場合がある。
このプログラムは、low ← middle、high ← middle となっていて、正しい2分探索の low ← middle + 1、high ← middle - 1 になっていません。そのため、範囲が縮まらない場合があります。
ウ {3, 8} で 8 を探す:low=1、high=2、middle=(1+2)÷2 の商=1。data[1]=3 < 8 なので low ← 1。low も high も変わらず、同じことを永遠に繰り返します(ウ)。
ア {5} で 5:middle=1 ですぐ見つかります。
イ {3, 8} で 3:middle=1 ですぐ見つかります。
エ {-1, 3, 8} で -1:middle=2、3 > -1 なので high ← 2。次に middle=1 で見つかり 1 を返します。-1 が要素にあっても、戻り値の -1(見つからない)と混同するだけで、無限ループにはなりません。
トレースすると、ウだけ low・high・middle の値が変わらないまま回り続けるのが見えます。
解説と下の表はこのサイトが作成したものです(表は、正解の選択肢を入れたプログラムを実際に実行した結果です)。