Pythonの二分探索（バイナリサーチ）を徹底解説！反復法・再帰法による実装ステップバイステップガイド

Pythonの二分探索（バイナリサーチ）は、ソート済みの配列から特定の要素の位置を効率的に見つけるためのアルゴリズムです。リストを半分に分割し、探している値が中央の値より大きければ右側を、小さければ左側を探索対象として絞り込んでいきます。

リストの中から特定の項目の位置を調べたいと思ったことはありませんか？そんなときに役立つのが二分探索です。二分探索を使えば、ソートされた配列内の要素の位置を簡単に特定できます。

コンピュータはリストから特定の項目を探すことが得意です。コンピュータがリスト内の項目を見つけるために使う規則のことを「探索アルゴリズム」と呼びます。Pythonで最も人気のあるアルゴリズムのひとつが、この二分探索です。

この記事では、二分探索とは何か、どのように動作するのかを解説し、実際にPythonでプログラムに組み込めるようになるまで、具体例を交えながら丁寧に説明していきます。それでは始めましょう！

Pythonの二分探索とは？

Pythonにおける二分探索とは、ソートされた配列の中から特定の要素の位置を見つけ出すアルゴリズムです。二分探索では、リストを繰り返し半分に分割し、そのたびに探している値が中央の値より大きいか小さいかを比較します。

二分探索の実装方法は主に2つあります。どちらの方法でも、配列内の現在の探索範囲における最高位置と最低位置を追跡するためのポインタを使用します。

1つ目は「反復法」です。この方法では、一連の処理を繰り返すことで要素の位置を特定します。Pythonではwhileループを使って実装するのが一般的です。

もう1つは「再帰法」です。これは、自分自身を呼び出し続ける関数を定義し、目的の要素が見つかるまで処理を繰り返す方法です。再帰法では「分割統治法」と呼ばれる考え方を利用し、要素が見つかるまで探索プロセスを繰り返します。

二分探索の仕組み：ステップバイステップ

分割統治や再帰といった話を聞いていると、二分探索が実際にどのように動くのかイメージしづらくなるかもしれません。そこで、ここからは具体的な例を使って二分探索の流れを確認していきましょう。次のリストを考えてみます。

7

9

14

22

34

このリストから「22」を探してみましょう。

まず、リストに2つのポインタを設定します。1つはリストの最小位置（Low）、もう1つは最大位置（High）を示します。

Low				High
7	9	14	22	34

次に、配列の中央の要素を求めます。この場合、中央は14です。もし中央の値が探している値と一致していれば、その値を返して終了です。

しかし今回は14と22は一致しないため、プログラムは比較処理を行う必要があります。

探している値が中央の値より大きい場合は、右側の範囲の中央と比較します。逆に小さい場合は、左側の範囲の中央と比較します。

22は14より大きいため、プログラムは右側の範囲へ移動します。右側の中央の要素は22であり、これはまさに探していた値です。

		Low	Middle	High
7	9	14	22	34

これで目的の値が見つかりました。プログラムはこの数値のインデックス位置を返します。この場合、22のインデックスは3です（リストのインデックスは0から始まることに注意してください！）。

Pythonで二分探索を実装する方法

それでは、実際にPythonコードを書いてみましょう。先ほど紹介した2つのアプローチ（反復法と再帰法）それぞれについて、二分探索の実装を見ていきます。

反復法による二分探索

まずは反復法から始めます。この方法では、リストの中間値を求めながらループ処理を続け、目的の値が見つかるまで探索を繰り返します。

二分探索関数の定義

まず、二分探索用のPython関数を定義しましょう。

def findValue(numbers, number_to_find):
    low = 0
    high = len(numbers) - 1

    while low <= high:
        middle = low + (high - low) // 2

        if numbers[middle] == number_to_find:
            return middle
        elif numbers[middle] < number_to_find:
            low = middle + 1
        else:
            high = middle - 1
    return -1

この関数は2つの引数を受け取ります。1つは検索対象のリスト、もう1つは見つけたい数値です。

続いて、リストの最低位置と最高位置の初期値を格納する2つの変数を宣言しています。lowは0（リストの先頭のインデックス）、highはリストの長さから1を引いた値（インデックスが0始まりであるため）に設定されます。

次にwhileループを宣言します。このループは、lowがhigh以下である限り実行され続けます。つまり、目的の数値がまだ見つかっていない間だけループが回るということです。

ループ内ではまず中央の値を計算します。highからlowを引き、その差を2で割った商（//演算子による整数除算）を求め、それをlowに加えることで中央のインデックスを算出しています。

リストの中央の値が探したい数値と一致していれば、その位置を返します。

中央の値が探したい数値より小さい場合は、lowを中央位置+1に更新します。これにより、探索範囲がリストの右側へ移動します。

逆に中央の値が探したい数値より大きい場合は、highを中央位置−1に更新します。これにより、探索範囲がリストの左側へ移動します。

この処理はlowがhigh以下である限り繰り返されます。最後まで値が見つからなかった場合は-1を返します。なぜ-1なのかは後ほど説明します。

探索の実行

次に、findValue関数の外側（プログラムの末尾）に以下のコードを追加します。

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find)

if final == -1:
    print("This item was not found in the list.")
else:
    print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

まず、検索対象となるリストを宣言し、続いて探したい数値として22を指定しています。

そしてfindValue()関数を呼び出し、リストと探したい数値を渡します。

ここで先ほどの-1が登場します。関数が-1を返した場合、それはリストの中に目的の項目が存在しなかったことを意味します。プログラマーはこのような場面でよく-1を使います。というのも、探索関数が返す有効なインデックスは決して負の数にならないからです。

-1以外が返された場合は、その値のインデックス位置を示すメッセージが出力されます。

このコードを実行すると、次の出力が得られます。

The number 22 was found at index position 3.

これで、数値22がインデックス3の位置にあることがわかりました。

再帰法による二分探索

二分探索は再帰を使っても実装できます。この方法では、「目的の数値が見つかる」という条件が満たされるまで、自分自身を呼び出し続ける関数を定義します。

再帰関数の定義

前の例と同様に、まず二分探索を行う関数を書きます。

def findValue(numbers, number_to_find, low, high):
    if high >= low:
        middle = low + (high - low) // 2

        if numbers[middle] == number_to_find:
            return middle
        elif numbers[middle] < number_to_find:
            return findValue(numbers, number_to_find, middle + 1, high)
        else:
            return findValue(numbers, number_to_find, low, middle - 1)
    else:
        return -1

コードの構造は前の例とかなり似ています。

最初に、highがlow以上であるかどうかをチェックします。そうでない場合（探索範囲がなくなった場合）は-1を返します。そうであれば二分探索を開始します。

中央の値の計算方法は前の例と同じです。highからlowを引き、その差を2で割った商を求め、lowに加えます。

その後、if文によって二分探索の進み方が決定されます。

• 中央の値が探している値と一致すれば、その位置を返します。
• 中央の値が探している値より小さければ、findValue()関数を再度呼び出します。このときlowの値は中央位置+1に設定されます。
• 中央の値が探している値より大きければ、findValue()関数を呼び出し、highの値を中央位置−1に設定します。

メインプログラムの作成

残るはメインプログラムを書くだけです。

numbers = [7, 9, 14, 22, 34]
number_to_find = 22

final = findValue(numbers, number_to_find, 0, len(numbers) - 1)

if final == -1:
    print("This item was not found in the list.")
else:
    print("The number " + str(number_to_find) + " was found at index position " + str(final) + ".")

メインプログラムは前の例とほぼ同じですが、1点だけ違いがあります。findValue()関数に新しくlowとhighという2つの引数を渡している点です。

これは、アルゴリズムが再帰的であるために必要な処理です。関数内でこれらの値を代入してしまうと、関数が実行されるたびに値がリセットされてしまい、探索アルゴリズムが正しく機能しなくなります。

このコードを実行すると、次の出力が得られます。

The number 22 was found at index position 3.

先ほどと同じ結果が得られました。この例では、反復処理ではなく再帰的なプログラムを使って二分探索を行いました。

二分探索はいつ使うべきか

二分探索は、数値のリストを検索する非常に効率的な方法です。先頭から順番に調べていく線形探索よりも高速です。これは、ソート済みリストの中央を見つけた時点で、探索範囲が半分に絞られるためです。

ただし重要な注意点があります。二分探索を使う前に、リストが必ず数値順にソートされている必要があります。二分探索を実行する前に、数値が昇順に並んでいることを必ず確認してください。

二分探索の計算量

二分探索の計算量はどのくらいなのでしょうか。良い質問ですね。

二分探索アルゴリズムの最良ケースの計算量はO(1)です。これは、最初の比較で目的の要素が見つかった場合に発生します。

平均ケースおよび最悪ケースの計算量はO(log n)です。つまり、リスト内の要素数が増えるにつれて、探索にかかる時間は対数的に増加します。例えば、100万件のデータから1件を探す場合でも、必要な比較回数はわずか20回程度で済むのです。これが二分探索が高速だと言われる理由です。

まとめ

二分探索は、リスト内の値のインデックス位置を効率的に見つけるための手法です。

二分探索が実行されるたびに、リストは2つの部分に分割されます。そして、探している値に近い側の半分だけに絞って探索を続けます。

探索が1回行われるごとに、プログラムが調べるべき数値の数は半分になっていきます。この特性こそが、二分探索が大規模なデータセットにおいて特に強力な理由です。