二分探索をツリーで可視化 — なぜ O(log n) か
ソート済みの配列を二分探索するとき、毎回まん中の値と比べて半分ずつ捨てていきます。この「まん中で分ける」を最後まで書き出すと、実は1本の木（決定木）になります。中央値がルート、左半分が左の部分木、右半分が右の部分木。探索とは、この木を上からたどる動きそのものです。だから比較回数は木の深さ＝およそ log₂n。これが O(log n) の正体です。下の配列と木は連動しています。
いま何をしているか
配列の二分探索が「木」になる理由
二分探索は、探す範囲 [左, 右] のまん中 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記法 で。
基本情報技術者試験ではこう出る
「二分探索の計算量（O(log n)）」「n個のデータを二分探索するときの最大比較回数」「二分探索の前提（整列済み）」が定番です。比較回数＝木の深さ＝log₂n と、上の木でイメージをつかんでおくと、丸暗記せずに答えられます。関連：探索アルゴリズム ／ 2分探索木 ／ 可視化一覧。