Pythonで学ぶ二分探索（バイナリサーチ）：仕組みと実装方法をわかりやすく解説

二分探索（バイナリサーチ）は、ソート済みの配列から特定の要素を効率的に検索するためのアルゴリズムです。ソートされていない配列には適用できない点に注意が必要です。二分探索は非常に効率的なアルゴリズムであり、計算量の面で線形探索を大きく上回る性能を発揮します。

線形探索の時間計算量は O(n) であるのに対し、二分探索の時間計算量は O(log n) です。つまり、データ量が増加しても検索時間の伸びが緩やかで、大規模なデータセットほどその効果を実感できます。ただし、あくまで「ソート済み」の配列にしか使えないという制約があります。

二分探索の仕組み

二分探索の基本的な考え方は、目的の要素を配列内のすべての要素と比較するのではなく、配列の中央の要素と比較するというものです。もし中央の要素が探している要素そのものであれば、検索はそこで成功です。そうでない場合、次のように判断できます。

• 探している要素が中央の要素より小さい場合 → 配列はソート済みなので、その要素は必ず配列の前半（左半分）に存在する
• 探している要素が中央の要素より大きい場合 → その要素は必ず配列の後半（右半分）に存在する

このように、二分探索は毎回検索範囲を半分に絞り込みながら進んでいきます。この処理は、目的の要素が見つかるまで、選択された範囲に対して繰り返し適用されます。

具体的には、まず左端のインデックス L を 0、右端のインデックス H を配列の最後のインデックスとして設定します。中央の要素のインデックス mid は、「(L + H) ÷ 2」で計算します。目的の要素が中央の要素より小さければ右インデックスを mid-1 に更新して前半だけを対象とし、大きければ左インデックスを mid+1 に更新して後半だけを対象とします。これを選択した範囲に対して繰り返すのが基本的な流れです。

要素が見つからないことはどう判断する？

要素が配列に存在しないことを判定するには、検索を停止するための条件が必要です。ここでは、左インデックスが右インデックス以下である間だけ検索を続けます。この条件が成立しなくなった（L > H となった）時点でまだ要素が見つかっていない場合、その要素は配列に存在しないと結論づけられます。

具体例：要素 6 を検索する

次のソート済み配列から、要素 6 を検索してみましょう。

L=0、H=8、Mid=4 として開始します。

6 < 10 なので、前半を対象にします。
H = Mid - 1 により、L=0、H=3、Mid=1 となります。

6 > 5 なので、今度は後半を対象にします。
L = Mid + 1 により、L=2、H=3、Mid=2 となります。

6 == 6 となり、要素が見つかりました。

以上の手順により、要素 6 はインデックス 2 の位置に存在することが確認できました。わずか3回の比較で見つけられた点に注目してください。

Pythonでの実装

ここでは、与えられたソート済み配列から目的の要素を検索し、要素が存在すればそのインデックスを出力し、存在しなければ -1 を出力するプログラムを作成します。

二分探索の実装コードは以下の通りです。

サンプルコード

def binary_search(arr,x):
    l=0
    r=len(arr)-1
    while(l<=r):
        mid=(l+r)//2
        if(arr[mid]==x):
            return mid
        elif(x<arr[mid]):
            r=mid-1
        elif(x>arr[mid]):
            l=mid+1
    return -1
array=[1,2,3,4,5,6,7,8,9,10]
a=7
print(binary_search(array,a))
b=15
print(binary_search(array,b))

実行結果

6
-1

要素 7 は配列のインデックス 6 に存在するため、6 が出力されました。

一方、要素 15 は配列内に存在しないため、-1 が出力されます。

まとめ

二分探索は、ソート済みデータを対象に、検索範囲を半分ずつ絞り込むことで高速に要素を見つけられるアルゴリズムです。時間計算量は O(log n) と線形探索の O(n) より大幅に優れており、大量のデータを扱う場面で真価を発揮します。一方で、事前にデータがソートされていることが前提となるため、使用場面には注意しましょう。Pythonでは上記のようなシンプルなコードで簡単に実装できるので、ぜひ実際に動かして挙動を確かめてみてください。