二分探索
整列済みのデータから目的の値を、探索範囲を毎回半分に切り捨てて高速に見つけます。
15
50
0
探索回数
0
残り候補数
—
線形探索なら
—
二分探索は「並んでいる」データ専用の検索法。先頭から順に見る線形探索が O(n) なのに対し、
二分探索は O(log n) ── 1000 件でも約 10 回、100 万件でも約 20 回で見つかります。
範囲の真ん中を見て、目的の値と比べる。目的の値が大きければ右半分、小さければ左半分に絞る。 これを繰り返すと、毎回候補が半分になります。
範囲の真ん中を見て、目的の値と比べる。目的の値が大きければ右半分、小さければ左半分に絞る。 これを繰り返すと、毎回候補が半分になります。
いまの探索
ここがポイント
- 二分探索が使える条件は データが整列済みであること。
- 1 回の比較で 候補が半分になる ── だから計算量は O(log n)。
- 探す値がデータに無い場合は、範囲が消える（lo > hi）と「見つからない」で終了。