FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説
問題
回転済み昇順配列 a={7,9,1,3,5} に対して、次の手続 rotatedSearch(a,3) を実行したときの戻り値はどれか。
○整数型: rotatedSearch(整数型の配列: a, 整数型: key)
整数型: left ← 1, right ← aの要素数, mid
while (left ≦ right)
mid ← (left ＋ right) ÷ 2 の商
if (a[mid] = key)
return mid
endif
if (a[left] ≦ a[mid])
if (a[left] ≦ key and key ＜ a[mid])
right ← mid － 1
else
left ← mid ＋ 1
endif
else
if (a[mid] ＜ key and key ≦ a[right])
left ← mid ＋ 1
else
right ← mid － 1
endif
endif
endwhile
return 0- ア 3
- イ 4
- ウ 5
- エ 0
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：4
正解：4
最初は left=1,right=5,mid=3 で a[3]=1。a[left]=7≦a[mid]=1 は偽なので右側が整列範囲。key=3 は a[mid]=1 より大きく a[right]=5 以下なので left=4 にする。次に mid=4 で a[4]=3 となり、戻り値は4。
3は最初のmidを答えにした誤り。5は右側範囲にあることだけを見て端を返した場合、0は回転配列を通常の二分探索として誤って追った場合に出やすい。
回転配列の探索では、左右どちらが整列しているかを先に判定する。keyがその整列範囲に入るかで探索範囲を絞る。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。