FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
次の探索で，keyより大きい最初の要素番号を求める。戻り値はどれか。
整数型の配列: a ← {1, 2, 2, 2, 4, 5}
整数型: key ← 2
整数型: left ← 1, right ← aの要素数 + 1, mid
while (left ＜ right)
mid ← (left ＋ right) ÷ 2
if (a[mid] ＞ key)
right ← mid
else
left ← mid ＋ 1
endif
endwhile
return left- ア 2
- イ 4
- ウ 5
- エ 6
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：5
正解：5
これはkeyと等しい位置ではなく，keyより大きい最初の位置を探すupper_boundである。a[mid]がkey以下なら，その位置は答えにならないのでleftをmid+1へ進める。
| left | right | mid | 判定 |
|---|---|---|---|
| 1 | 7 | 4 | a[4]=2 → left=5 |
| 5 | 7 | 6 | a[6]=5 → right=6 |
| 5 | 6 | 5 | a[5]=4 → right=5 |
終了時left=5なので戻り値は5。2が最初に出る位置ではない点が引っかけである。
選択肢の見分け方：2はlower_boundの答え，4は最後の2の位置，6は5の位置である。ここではkeyより大きい最初の位置を探しているため，答えは4の位置である5になる。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。