二分探索 — 真ん中を見て、半分を捨てる
辞書で「さ」で始まる言葉を引くとき、1ページ目から順にめくる人はいません。だいたい真ん中を開いて、「行きすぎた」「まだ手前だ」と半分に絞り込むはずです。これと同じことを、並べ替え済みのデータに対して機械的にやるのが二分探索です。
ポイントはたった1つ。真ん中を見て、探す値と比べ、いらない半分を丸ごと捨てる。これを繰り返すだけ。下の図1で、探したい数字のカードを選んで「次の一歩」を押してみてください。1回比べるたびに、候補がごっそり半分に減っていきます。
DATA — 小さい順に並んだ16個の数字(カードを選ぶと探す値になります)
まだ候補
いま比べる中央
捨てた範囲
見つけた
探す値 42
真ん中を見て、半分に絞る
「次の一歩」を押すと、いまの候補範囲の真ん中(中央)を1回だけ調べます。探す値より小さければ左半分を、大きければ右半分を、まるごと捨てます。
二分探索の比較回数 0
残っている候補 16 個
先頭から数えると 10 番目
図1 — 二分探索:1回比べるたびに候補が半分になる
なぜ「半分」がそんなに効くのか
16個なら、最悪でも4回で答えにたどり着きます(16→8→4→2→1)。先頭から1つずつ調べる線形探索なら最悪16回。差はわずかに見えますが、データが増えるほど開きは劇的になります。100万個でもたった20回ほど。1回ごとに候補が半分になる、つまり調べる回数がデータ量の「桁数」くらいで済む(O(log n))からです。
ただし二分探索には絶対条件があります。データが並べ替え済みであること。順番がバラバラだと「真ん中より大きい=右にある」という前提が崩れ、半分を捨てる判断ができません。だからこそ、何度も検索するデータはあらかじめ並べておく(=インデックスを張る)価値があるのです。
用語ミニ辞書
- 線形探索
- 先頭から1つずつ順に調べる方法。並べ替え不要だが、最悪は全件分の回数がかかる。
- 二分探索
- 並べ替え済みデータの真ん中と比べ、半分ずつ候補を捨てる方法。回数は O(log n)。
- O(log n)
- データが倍になっても、調べる回数は1回しか増えない、という増え方の少なさ。
まとめ
二分探索は「真ん中を見て、いらない半分を捨てる」を繰り返すだけのシンプルな考え方です。それでもデータ量が膨らんだときの強さは圧倒的で、データベースのインデックス(B+Tree)や、ソート済み配列への検索など、あらゆる場所で土台になっています。速さの正体は、毎回半分を即座に切り捨てる思い切りの良さにあります。