応用情報技術者 2011年 秋期 午前2 問08
問題文
データが昇順にソートされた配列Xiを2分探索する。流れ図のaに入るものとして、適切なものはどれか。ここで、流れ図の中の割り算は小数点以下を切り捨てるものとする。
選択肢
ア：left < right
イ：left ≦ right（正解）
ウ：left + 1 < right
エ：left + 1 ≦ right
データが昇順にソートされた配列X[i]を2分探索する【午前2 解説】
要点まとめ
- 結論：ループ継続条件は「left ≦ right」が正解で、探索範囲が空になるまで繰り返す必要があります。
- 根拠：2分探索は探索範囲の左右端を示すleftとrightの位置関係で判定し、leftがrightを超えたら探索終了です。
- 差がつくポイント：条件を「left < right」にすると、探索範囲が1要素のときにループが終了し、正しく探索できません。
正解の理由
選択肢イの「left ≦ right」は、探索範囲が1要素のときもループを継続し、その要素をチェックできるため正解です。2分探索は範囲内に探索値が存在するかを調べるため、範囲が空になる（left > right）まで繰り返す必要があります。leftとrightが等しい場合も探索対象があるため、ループを続ける条件に含めるのが正しいです。
よくある誤解
「left < right」とすると、探索範囲が1つの要素のときにループが終了し、最後の要素を調べられず誤答になります。これが最も多い誤解です。
解法ステップ
- 探索範囲の初期値をleft=0、right=n-1に設定する。
- ループ条件を「sch == -1 かつ left ≦ right」とする。
- 中央のインデックスcenterを計算し、X[center]と探索値を比較する。
- 探索値がX[center]より小さければrightをcenter-1に更新。
- 探索値がX[center]より大きければleftをcenter+1に更新。
- 探索値と一致すればschにcenterを代入しループ終了。
- leftがrightを超えたら探索終了し、見つからなかったことを示す。
選択肢別の誤答解説
- ア: left < right
範囲が1要素のときループが終了し、最後の要素を調べられません。 - イ: left ≦ right
正解。範囲が1要素のときもループ継続し、正しく探索可能です。 - ウ: left + 1 < right
範囲が2要素以下のときループが終了し、正しく探索できません。 - エ: left + 1 ≦ right
範囲が2要素のときのみループ継続し、1要素のときに終了してしまいます。
補足コラム
2分探索はソート済み配列の高速探索アルゴリズムで、計算量はです。ループ条件の設定ミスは探索漏れや無限ループの原因になるため、正確な条件設定が重要です。整数除算で切り捨てるcenter計算も基本的なポイントです。
FAQ
Q: なぜ「left ≦ right」が必要なのですか？
A: 探索範囲が1要素のときも調べるため、leftとrightが等しい場合はループを続ける必要があります。
A: 探索範囲が1要素のときも調べるため、leftとrightが等しい場合はループを続ける必要があります。
Q: 「left < right」では何が問題ですか？
A: 範囲が1要素のときループが終了し、最後の要素をチェックできず誤った結果になります。
A: 範囲が1要素のときループが終了し、最後の要素をチェックできず誤った結果になります。
関連キーワード: 2分探索、バイナリサーチ、ソート済み配列、探索アルゴリズム、ループ条件
\ せっかくなら /
応用情報技術者を
クイズ形式で学習しませんか？
クイズ画面へ遷移する→
すぐに利用可能！