平成23年度秋期 応用情報技術者試験 午前 問8
データが昇順にソートされた配列X[i]（i＝0,1,…,n-1）を2分探索する。流れ図のaに入るものとして，適切なものはどれか。ここで，流れ図の中の割り算は小数点以下を切り捨てるものとする。
- ア left＜right
- イ left≦right
- ウ left＋1＜right
- エ left＋1≦right
解答・解説を見る
正解：イ
AI解説
2分探索は探索範囲の下限leftと上限rightを保ちながら中央値と比較して範囲を半分に絞る。範囲に要素が残っている条件はleft≦rightであり、これがループの継続条件aに入る。left>rightになった時点で「見つからずに終了」と判断する。したがってイが正解である。 ア: left＜rightでは、left=rightで範囲に要素が1個だけ残っているケースを検査せずに終了してしまい、その要素が目的値のとき探索に失敗する。 イ: 正しい。left≦rightの間は未検査の要素が存在するため、ループを継続する。 ウ: left+1＜rightでは範囲に1〜2個残った時点で終了してしまい、探索漏れが生じる。 エ: left+1≦rightはleft＜rightと同値であり、アと同様に要素1個のケースを取りこぼす。 💡 2分探索の境界条件は「=を含むか」が定番の引っかけ。left=right(残り1件)をまだ調べるべきかを具体例(要素1個の配列)で確かめると確実に判断できる。
出典：平成23年度 秋期 応用情報技術者試験 午前 問8 ／ 独立行政法人情報処理推進機構（IPA）
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。
※Web掲載用に表記を一部変更しています。図表はIPA公式問題冊子から引用しています。著作権はIPAに帰属します。