二分探索と整列条件: 原理・関係式・例

概念と仕組み

線形探索は、値を順に調べますが、二分探索は現在の範囲の中央値を調べます。目標値よりも中央値が大きいか小さいかを知っていれば、ソートされた順序を利用して、範囲の半分を排除できます。

以下の比較において、答えが存在する場合、その答えは残りの範囲内に存在しなければなりません。範囲が空になった場合、その範囲内に値が存在しないと結論付けます。

候補の数は、約 n/2ᵏ で減少するため、比較の数は対数的に増加する。シミュレーションにおける、n≥1 で重複がないリストの場合、最大となる比較の数は、⌊log₂n⌋ + 1 と比較できる。

ソートのコストと検索コストは、それぞれ個別に考慮する必要があります。重複値を持つリストにおける、最初の位置と最後の位置を特定する問題に取り組みする場合、停止条件を調整する必要があります。

二分探索は比較ごとに候補範囲を半分にします。

重複のない整列済み整数列を両手法で使います。

binary steps ≤ ⌊log₂n⌋ + 1

式で使う記号と単位
記号	意味	単位
n	データ数	個
k	比較・探索範囲の縮小回数	回

整列済みリスト · 二分探索は比較ごとに候補範囲を半分にします。

1つの変数を変えて基準記録と比べます。