FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
回転済みの昇順配列からkeyを探す。次のプログラムを実行したとき，戻り値はどれか。配列の要素番号は1から始まる。
整数型の配列: a ← {6, 8, 1, 3, 5}
整数型: key ← 3
整数型: left ← 1, right ← 5, mid
while (left ≦ right)
mid ← (left ＋ right) ÷ 2
if (a[mid] = key)
return mid
endif
if (a[left] ≦ a[mid])
if (a[left] ≦ key かつ key ＜ a[mid])
right ← mid － 1
else
left ← mid ＋ 1
endif
else
if (a[mid] ＜ key かつ key ≦ a[right])
left ← mid ＋ 1
else
right ← mid － 1
endif
endif
endwhile
return 0- ア 0
- イ 3
- ウ 4
- エ 5
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.x 科目B範囲
正解と解説
正解：4
正解：4
1回目はleft=1,right=5,mid=3でa[3]=1。左側は昇順ではなく，右側1,3,5が昇順。key=3は右側にあるためleft=4にする。
2回目はmid=4でa[4]=3となり，keyと一致するので4を返す。
Hardでの確認点：回転配列では，単純にkeyとa[mid]だけを比べない。midの左右どちらが昇順になっているかを判定し，keyがその範囲に入るかでleft/rightを更新する。
追加の確認：Hard問題では、正解値だけでなく、途中の更新規則を一つずつ確認する。どの条件で変数・添字・候補集合が変わるのかを見落とすと、もっともらしい選択肢に引っかかりやすい。
この問題について
擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。