基本情報技術者試験基礎・応用
テーマ 08 / 86
二分探索の前提
ここだけ覚える二分探索は整列済みの探索範囲を比較によって半分に絞る。
順番に考える
- 1整列の前提
- 2中央と比較
- 3対象を含む側に絞る
間違えやすいところ
未整列の配列へ同じ手順をそのまま使うと正しく探せません。
問題で確かめる
昇順の配列で中央値より探す値が大きい。次に対象とする範囲はどれか。
答え・解き方を読む
中央より後ろの範囲
図で考え方を確認
候補区間を半分へ絞り続ける
図を拡大して見る ↗整列済みという前提で中点と比較し候補を狭めます。境界探索のlo/hiはどちらを含むかを設問のコードで確認します。単に添字から位置を計算する問題では、この図を使いません。
図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。
二分探索は整列済みの探索範囲を比較によって半分に絞る。 未整列の配列へ同じ手順をそのまま使うと正しく探せません。