FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：回転済み昇順配列 a={7,9,1,3,5} に対して、次の…
問題
回転済み昇順配列 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
最初は 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がその整列範囲に入るかで探索範囲を絞りましょう。
つまずきポイント：このコードは回転済み昇順配列に対する二分探索で、要素に重複がない前提で成り立ちます。a[left]≦a[mid]の比較で整列している側を一意に決められるからで、計算量はO(log n)です。もし等しい値が混ざると整列側を判定できず、最悪O(n)まで悪化する点に注意しましょう。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。