https://pydocument.hatenablog.com/entry/2023/03/26/224239

二分探索はソート済みの配列から特定の値を効率的に検索するアルゴリズムです。Python ではリストなどに対して二分探索を適用できます。この記事では、Python で二分探索を実装する複数の方法を解説ます。

二分探索の概要

二分探索は、昇順または降順にソートされた配列（リスト）の中から目的の値を効率的に見つけるアルゴリズムです。

アルゴリズムの手順

配列の中央の要素を選択します。
中央の要素と探している値を比較します。
探している値が中央の要素と一致すれば探索成功です。
探している値が中央の要素より大きければ、中央より右側（昇順の場合）の配列に対して、1. からの手順を繰り返します。
探している値が中央の要素より小さければ、中央より左側（昇順の場合）の配列に対して、1. からの手順を繰り返します。
探索範囲がなくなるまで上記を繰り返し、それでも見つからなければ探索失敗です。

具体例 ソート済みの配列 [1, 3, 5, 7, 9] から 7 を探す場合を考えます。

中央の要素 5 と 7 を比較します。
7 は 5 より大きいので、右側の [7, 9] を探索します。
[7, 9] の中央の要素 7 と 7 が一致するので探索成功。7 はインデックス 3 にあることがわかります。

特徴

時間計算量: O(log n) であり、線形探索 (O(n)) に比べて高速です。
前提条件: 配列がソート済みである必要があります。
注意点
- 配列の要素が更新された場合は、再度ソートが必要です。
- 重複する要素がある場合、最初に見つかった要素のインデックスが返されます（必ずしも特定の位置にある要素を返すとは限りません）。

`bisect` モジュールの利用

Python の標準ライブラリ bisect は、二分探索をサポートする関数を提供しています。

`bisect_left` 関数

bisect_left(arr, x) 関数は、ソート済みの配列 arr に対して、値 x を挿入できる最も左側のインデックスを返します。この関数を利用することで、x が配列内に存在するかどうか、そして存在する場合はそのインデックスを知ることができます。

実例

ソート済みリスト arr 内で値 x を検索します。 bisect.bisect_left(arr, x) で x を挿入できる最も左のインデックスを取得します。取得したインデックスがリストの範囲内であり、かつその位置の値が x と等しければ、そのインデックスは x が存在する位置です。そうでない場合は、x はリスト内に存在しないということです。

import bisect

def binary_search(arr, x):
    i = bisect.bisect_left(arr, x)
    if i != len(arr) and arr[i] == x:
        return i
    else:
        return -1

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
print(binary_search(arr, x))

x = 10
print(binary_search(arr, x))

二分探索の自作関数

二分探索は再帰関数を用いて自作することも可能です。low と high は探索範囲の開始と終了のインデックスです。mid は low と high の中間点で、// 演算子で整数除算を行います。この計算の再帰呼び出しにより探索範囲を狭めていきます。

再帰関数による実装

def binary_search_recursive(arr, low, high, x):
    if high >= low:
        mid = (high + low) // 2  # 中央のインデックス

        if arr[mid] == x:
            return mid  # 中央の要素が目的の値と一致
        elif arr[mid] > x:
            return binary_search_recursive(arr, low, mid - 1, x)  # 左側を探索
        else:
            return binary_search_recursive(arr, mid + 1, high, x)  # 右側を探索
    else:
        return -1  # 見つからない場合

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5

print(binary_search_recursive(arr, 0, len(arr) - 1, x))

反復処理による実装

再帰を使わずに、while ループを使って二分探索を実装することも可能です。

def binary_search_iterative(arr, x):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
x = 5
print(binary_search_iterative(arr,x))

各実装方法の比較

実装方法	特徴	注意点
`bisect` モジュール	簡潔で高速。	`bisect` モジュールに馴染みがないと理解しにくい場合がある。
自作関数（再帰）	アルゴリズムの理解がしやすい。	大規模な配列ではスタックオーバーフローの可能性がある。
自作関数（反復処理）	再帰版に比べてスタックオーバーフローの心配がない。アルゴリズムの理解もしやすい。	再帰版に比べてコードが少し長くなることがある。

まとめ

Python で二分探索を実装する方法として、bisect モジュールを使う方法と、自作関数を使う方法 (再帰、反復) があります。それぞれの特徴を理解し使い分けることが重要です。

bisect モジュール: 簡潔さと速度が求められる場合に適しています。
自作関数 (再帰/反復): アルゴリズムの理解を深めたい場合や、bisect モジュールにない特殊な要件がある場合に適しています。

いずれの場合も、二分探索は配列がソート済みであるという前提条件を満たす必要があることに注意してください。

[PR]

click.linksynergy.com