二分探索 Binary Search
整列済みの配列に対して、探索範囲の中央 mid と target を比較します。一致すれば終了、target が大きければ右半分、小さければ左半分へ範囲を絞り、これを繰り返します。
1回の比較で候補が半分になるため、計算量は O(log n)。low・mid・high の3つのポインタがどう範囲を狭めていくかに注目しましょう。配列は昇順に整列している必要があります。
※ 二分探索は昇順前提のため、自動で昇順に整列して実行します
▶📖 記号の読み方（はじめての人はここを確認）
←代入（右の値を左の箱に入れる）。例: 合計 ← 0
=等しいか比べる（代入ではない）
≠等しくない（≠ は != と書いてもOK）
≤ / ≥以下 / 以上（<= / >= でもOK）
×かけ算（* でもOK）
÷わり算。答えの小数は捨てる（例: 7÷2=3）。/ でもOK
%わり算の余り（例: 7%2=1）
要素数(配列)配列の箱の数。2次元では 行数()・列数()
▲i / ▲j配列の下の三角は「いまコードが見ている位置」
algorithm.pseudo擬似言語 / IPA形式
1整数型の配列: data2整数型: low, high, mid, target, 結果3low ← 14high ← 要素数(data)5結果 ← -16while (low ≤ high and 結果 = -1)7 mid ← (low + high) ÷ 28 if (data[mid] = target)9 結果 ← mid10 elseif (data[mid] < target)11 low ← mid + 112 else13 high ← mid - 114 endif15endwhile
▶ 実行を開始します
配列の可視化
箱の番号（添字）は 1 から始まります▶ 整数型の配列: data
実行を開始します
data
1
[1]
4
[2]
9
[3]
16
[4]
25
[5]
36
[6]
49
[7]
64
[8]
81
[9]
← よこにスクロールできます →
まだ見ていないいま見ている数字を書きかえた完了
マスの下の ▲i は「いまコードが見ている位置」・ 棒の高さは数の大きさ
くらべた回数
0
書きかえた回数
0
読んだ回数
0
変数の状態（いまの値）
low=—
範囲の左はし
mid=—
範囲のまん中
high=—
範囲の右はし
target=36
探す値
結果=—
見つかった位置（無ければ-1）
1 / 21
速度
理解度チェック
解答すると、そのアルゴリズムが実際に動く様子を再生して確認できます。
確認問題 1
要素数 1,000,000 のソート済み配列を二分探索するとき、最悪でも必要な比較回数はおよそ何回か。
確認問題 2
二分探索を正しく適用するための前提条件はどれか。
▶📊 計算量（速さの目安）— くわしく知りたい人向け
「計算量」は、データが増えたときに手間（時間）がどれくらい増えるかの目安です。n はデータの個数。記号の意味は各カードの下に書いてあります。
最良（いちばん速い場合）
O(1)
データが増えても一定（最速）
平均（ふつう）
O(log n)
データが倍でも手間は1回ぶん増えるだけ（とても速い）
最悪（いちばん遅い場合）
O(log n)
データが倍でも手間は1回ぶん増えるだけ（とても速い）
使う追加メモリ（空間）
O(1)
データが増えても一定（最速）