QUESTION 10
昇順に整列された配列を二分探索する。中央の要素が目的の値と一致せず、次の探索を続けるとき、候補となる範囲は原則としてどう変化するか。
出典：本サイト オリジナル教材（2026年）
本サイトで独自に作成。IPAの試験問題からの転載ではありません。
公開日：
選択肢を選んで、答え合わせをしましょう。
回答せずに正解・解説を確認する
正解：イ 約半分になる
この表示だけでは、回答数や正答率は変わりません。
解説
中央の要素と目的の値を比較し、値が存在し得ない側を除外します。毎回およそ半分に範囲が縮まるため、大きな配列でも効率よく探索できます。
ア
一つずつ確認する逐次探索とは異なります。
イ
中央を境に片側を除外するため、約半分です。
ウ
比較するごとに候補は減少します。
エ
範囲を狭めなければ探索は進みません。
関連知識
要素数nに対する二分探索の最悪時の比較回数はO(log n)です。探索前に対象が同じ順序で整列されていることが前提で、未整列の配列へそのまま適用してはいけません。
間違えやすいポイント
見つかったときは終了します。「約半分」は、見つからず次の探索を続ける場合の候補数です。
覚え方
中央で比較し、不要な半分を捨てる。
実務での意味
整列されたID一覧から候補を探すときに利用できます。更新や整列のコストも含めて方式を選びます。
解説：本サイト編集部によるオリジナル文章