情報・コンピューティング · アルゴリズム探究 / 原理と探究
線形探索と二分探索 実験解説
整列済みリストの候補範囲と比較位置を観察します。
どのような原理？
二分探索は比較ごとに候補範囲を半分にします。
重要な関係
binary steps ≤ ⌊log₂n⌋ + 1
観察してみよう
- 整列済みリストの候補範囲と比較位置を観察します。
- 3つの基準条件を実行して記録します。
- 1つの変数を変えて基準記録と比べます。
結果を読み解く
二分探索に必要な条件は？
整列済みリスト · 二分探索は比較ごとに候補範囲を半分にします。
モデルの仮定と限界
重複のない整列済み整数列を両手法で使います。