二分探索について（アルゴリズム）

二分探索とは

二分探索（英: binary search）もしくはバイナリサーチとは、計算機科学において整列配列の中から目標の値の位置を見つけ出す探索アルゴリズム。このアルゴリズムでは、探索目標と、配列の中央に位置する要素とをまず比較する。値が等しくない場合、目標が存在する可能性がない側の半分の部分配列を除外し、残りの半分について中央要素との比較を再び行う。この手続きを目標値が見つかるまで繰り返す。配列が空になって終了したなら、元の配列に目標値が存在しなかったということである。

二分探索は対数時間で動作するアルゴリズムであり、最悪のケースにおいて比較演算を O(log n)回行う（ n は配列の要素数）。二分探索は配列が特に小さくなければ線形探索より高速であるが、実行するには配列があらかじめソートされていなければならない。ハッシュテーブルのように探索速度に特化したデータ構造ならば二分探索よりも効率よく探索を行うことができるが、二分探索は配列に目標の値が含まれない場合に最近傍の値を見つけるような応用がある。
二分探索 - Wikipediaより一部抜粋

二分探索の動きは？

連続した値で1 ~ 10の数字があるとします。4を探したい時は、4と中央値の5を比較します。
この時、3パターンがある

1. 中央値より低い
2. 中央値より高い
3. 中央値と同じ

4の場合は、中央値より低いためパターン1に該当する。

1	2	3	4	5	6	7	8	9	10

中央値の5と比較した結果、4は5より小さいとわかりました。
この時点で5は「4ではない」と確認済みなので、5も含めて捨てます。
そのため次の探索範囲は1〜4になります。
中央値は2となり、4は中央値より大きいです。

1	2	3	4

この時点で2は「4ではない」と確認済みなので、2も含めて2以下を捨てます。
そのため次の探索範囲は3〜4になります。
3〜4では中央値は3となり、4は中央値より大きいです。

3	4

この時点で3は「4ではない」と確認済みなので、3も含めて3以下を捨てます。
そのため次の探索範囲は4のみになり、4 == 4 で発見です。

4

コードを見てみよう

Python

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2  # 中央のインデックス

        if arr[mid] == target:
            return mid              # 発見！
        elif target > arr[mid]:
            left = mid + 1          # 中央値より大きい → 中央値以下を捨てる
        else:
            right = mid - 1         # 中央値より小さい → 中央値以上を捨てる

    return -1  # 見つからなかった

線形探索と比べてみよう

線形探索は先頭から順番に1つずつ確認していきます。最悪の場合、探している値が末尾にあると全件チェックが必要です。
10を探す場合、1から順番に全てチェックするため10回かかります。
一方、二分探索だと最大4回で済みます。

1	2	3	4	5	6	7	8	9	10

また要素の数が多いほど二分探索は有効です。
100万のデータ数だと最大20回で済みます。

logってなに？

logとは「ある数を何乗すれば目標の数になるか」を表す数学の概念です。
例えば log₁₀(1000) = 3 は 「10を3回かけると1000になる」 という意味です。

計算	結果
10¹	10
10²	100
10³	1000

アルゴリズムでのlog₂とは？

アルゴリズムの世界では2を底とするlog₂がよく登場します。
これは 「nを2で何回割ったら1になるか」 を表します。
二分探索は毎回半分に絞るので

ステップ	計算	残りの要素数
1回目	10 ÷ 2	5
2回目	5 ÷ 2	2
3回目	2 ÷ 2	1

「何回2で割ったら1になるか」が探索回数の目安です。発見時の比較を含めると最大4回になります。

「何回2で割ったら1になるか」= 探索回数の上限、これを log₂(n) で表しています。

二分探索の注意点

二分探索を使うには配列がソート済みであることが前提です。
例えば以下のようなバラバラの配列では正しく動きません。

3	7	1	9	5	2	8	4	6	10

中央値の5と比較して「4は5より小さいから左半分を探す」としても、左半分に4が存在する保証がないためです。
二分探索を使う前に必ずソート（基本は昇順）しておく必要があります。

まとめ

• 二分探索は毎回半分に絞ることで効率よく探索できる
• 線形探索より速く、100万件でも最大20回で済む
• 使う前に配列がソート済みであることが前提