1 歩ずつ動かす
配列 [3, 8, 12, 17, 23, 31, 42, 56] から 42 を探す
- 30
- 81
- 122
- 173
- 234
- 315
- 426
- 567
- 比較中
- 発見
- 対象外
- いまの範囲
- 箱の下の数字は添字
二分探索は、配列が小さい順に並んでいる前提で動きます。並んでいない配列では正しく探せません。
1 歩目 / 全 7 歩比べた回数 0 回
探す値は 42 です。範囲は添字 0 から 7 までの全部です。
いま動いている疑似コードの行
- 1lo = 0, hi = n - 1
- 2lo <= hi のあいだ繰り返す
- 3mid = (lo + hi) を 2 で割った商
- 4もし a[mid] == x なら mid を返す
- 5もし a[mid] < x なら lo = mid + 1
- 6そうでなければ hi = mid - 1
- 7-1 を返す (見つからない)
見本を変える
予想してみる
いまは 1 歩目です。
次に比べるのは、どの添字でしょう。
今回わかること
- 真ん中と比べて、探す範囲を半分ずつ狭める流れ
- 8 個でも 100 万個でも、比べる回数が少なく済む理由
前提
- 線形探索の流れ
- 配列と添字 (0 から数える番号)
- while 文と、割り算の商
どんな探し方か
二分探索は、並んだ配列の真ん中と比べ、目当ての値が左右どちらにあるかを決めて、範囲を半分に狭める探し方です。
1 回比べるごとに候補が半分になるので、配列が大きくなっても比べる回数はあまり増えません。
手順と具体例
- 1範囲を配列全体にする (lo を 0、hi を右端の添字に)
- 2範囲の真ん中 mid の値と、探す値を比べる
- 3同じなら、mid を答えにして終わる
- 4真ん中のほうが小さければ右半分へ、大きければ左半分へ範囲を狭める
- 5範囲が空になったら「見つからない」で終わる
| 回 | 範囲と真ん中 | 結果 |
|---|---|---|
| 1 | 範囲 0〜7添字 3 の 17 | 小さい。右半分へ |
| 2 | 範囲 4〜7添字 5 の 31 | 小さい。右半分へ |
| 3 | 範囲 6〜7添字 6 の 42 | 同じ。見つかった |
比べる回数と計算量
| 場合 | 比べる回数 | 計算量 |
|---|---|---|
| いちばん速い | 1 回 (最初の真ん中) | O(1) |
| 平均 | およそ log₂ n 回 | O(log n) |
| いちばん遅い | およそ log₂ n + 1 回 | O(log n) |
8 個なら最悪 4 回、100 万個でも最悪 20 回ほどです。線形探索なら 100 万個で最悪 100 万回なので、差は大きく開きます。
| 探す値 | 線形探索 | 二分探索 |
|---|---|---|
| 42 | 7 回 | 3 回 |
| 20 | 8 回 | 3 回 |
| 3 | 1 回 | 3 回 |
| 56 | 8 回 | 4 回 |
使いどころ
向いているとき
- 配列がすでに小さい順に並んでいるとき
- 同じ配列から何度も探すとき (最初に 1 回並べれば、あとは速い)
- 「この値以上の最初の位置」のような境目を探すとき
向いていないとき
- 配列が並んでいないとき (並べ替えの手間のほうが大きくなる)
- 追加や削除が多く、並びを保つのが大変なとき
コード
疑似コード
- 1lo = 0, hi = n - 1
- 2lo <= hi のあいだ繰り返す
- 3mid = (lo + hi) を 2 で割った商
- 4もし a[mid] == x なら mid を返す
- 5もし a[mid] < x なら lo = mid + 1
- 6そうでなければ hi = mid - 1
- 7-1 を返す (見つからない)
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- 並んでいない配列で使うと、どうなりますか？
- 真ん中との大小で左右を決めるので、答えがある側を捨ててしまいます。エラーにはならず、ある値を「無い」と返すことがあります。
- Java のコードだけ mid の計算が違うのはなぜですか？
- lo + hi が int の上限を超えるのを防ぐためです。lo + (hi - lo) / 2 は同じ値になり、足し算があふれません。
- 真ん中が 2 つあるときは、どちらを見ますか？
- 要素が偶数個だと真ん中が 2 つになります。ここでは商を切り捨てるので、左側を見ます。
