二分探索をツリーで可視化 — なぜ O(log n) か
ソート済みの配列を二分探索するとき、毎回まん中の値と比べて半分ずつ捨てていきます。この「まん中で分ける」を最後まで書き出すと、実は1本の木（決定木）になります。中央値がルート、左半分が左の部分木、右半分が右の部分木。探索とは、この木を上からたどる動きそのものです。だから比較回数は木の深さ＝およそ log₂n。これが O(log n) の正体です。下の配列と木は連動しています。
いま何をしているか
使い方
要素数（7・15・31）を選ぶと、整列済みの配列とそれに対応する木が表示されます。「探す値」を入れて「探索」を押すと、ルートから順に比べていく道筋が光ります。「🎲 別の配列で」で、値を入れ替えて何度でも試せます。
配列の二分探索が「木」になる理由
二分探索は、探す範囲 [左, 右] のまん中 mid をまず調べます。この mid を根（ルート）とし、「もっと小さいかも」の左半分 [左, mid-1] を左の部分木、「もっと大きいかも」の右半分 [mid+1, 右] を右の部分木として、同じことを繰り返す——こうしてできるのが上の木です。ソート済みの配列から機械的に決まるので、いつも左右がきれいに釣り合った（バランスの取れた）木になります。
探索＝木を上からたどる／比較回数＝木の深さ
探す値をルートと比べ、小さければ左の子、大きければ右の子へ。これは配列で「まん中と比べて半分を捨てる」のとまったく同じ動きです。見つかるまでにたどるノード数＝木の深さで、バランスの取れた木の深さは ⌈log₂(n+1)⌉。だから要素が2倍になっても、深さ（＝最悪の比較回数）は1増えるだけです。
| 要素数 n | 木の深さ（最悪の比較回数） |
|---|---|
| 15 | 4 |
| 1,000 | 約10 |
| 1,000,000 | 約20 |
100万個でも、深さ約20＝20回くらいの比較で見つかります。これが O(log n) の速さです。
2分探索木（BST）とのつながり
ここで描いた「理想的にバランスした木」は、まさに 2分探索木（BST） が目指す形です。BSTは値を挿入する順番しだいで木の形が変わり、1→2→3… と順に入れると一直線に伸びて実質は連結リストになり、探索が O(n) まで遅くなります。「ソート済み配列の二分探索＝つねに理想形のBST」と考えると、両者の関係がすっきりつながります。
🧩 関連する可視化：配列そのままで比べるなら 探索アルゴリズム（線形 vs 二分）、データ構造としての木は 2分探索木、速さの測り方は 計算量とO記法 で。
最大比較回数の求め方
n個のデータを二分探索するときの最大比較回数は、log2n の小数点以下を切り捨てて1を足した数です。この可視化で選べる7・15・31個は、それぞれ深さ3・4・5の木がちょうど埋まる個数（2k−1）です。
| 要素数 n | 最大比較回数 |
|---|---|
| 7 | 3回 |
| 15 | 4回 |
| 31 | 5回 |
| 1,000 | 10回 |
| 1,000,000 | 20回 |
二分探索が使えない場面
- データが並んでいない：まん中と比べて半分を捨てる前提が成り立ちません。並べ替えてから使うか、線形探索を使います。
- まん中に直接行けない：連結リストのように先頭から順にたどるしかないデータ構造では、まん中を見るだけで時間がかかり、速さが生きません。
- データがひんぱんに増減する：追加のたびに並べ直すのは手間がかかるので、2分探索木やハッシュ表を使うのが一般的です。
基本情報技術者試験ではこう出る
「二分探索の計算量（O(log n)）」「n個のデータを二分探索するときの最大比較回数」「二分探索の前提（整列済み）」がよく問われます。比較回数＝木の深さ＝log₂n と、上の木でイメージをつかんでおくと、丸暗記せずに答えられます。関連：探索アルゴリズム ／ 2分探索木 ／ 可視化一覧。
よくある質問
Q. 二分探索の平均比較回数は？
A. 最大比較回数より少し少なくなります。基本情報技術者試験では、平均を「およそ log₂n 回」として扱うことが多いので、最大と平均のどちらを聞かれているかを問題文で確かめてください。