Python を使用して二分探索を実装する方法-Python チュートリアル-php.cn

Python を使用して二分探索を実装する方法

WBOY

リリース： 2023-05-11 10:40:05

転載

3252 人が閲覧しました

まず、binary_search という名前の関数を作成します。要素のリストと検索する値の 2 つのパラメーターを渡します。

def binary_search(_list, value):

ログイン後にコピー

次に、関数内で必要な変数を定義します。二分法のポイントは、リストの中央から両側に向かって検索することです (厳密な表現ではないかもしれませんが、おそらくこれが意味します)。したがって、直感のために、 left 、 right 、および Mid は、それぞれリストの開始インデックス、終了インデックス、中間インデックスを表す 3 つの変数であると定義します。

    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置

ログイン後にコピー

次のステップは二分探索の重要な部分の実装です。まず探索がスムーズに進むようにwhileループを定義します。while関数の中にif分岐文をネストして条件判定を実装します。 3 つの状況:

1. _list[mid] == 値: たまたま中間の値が検索する必要がある値であるため、対応するインデックスを直接返します。

2. _list[mid] > value: 検索する値はmidの左側にあり、右側の値をmidに更新して検索範囲を絞ります。

3._list[mid] < value: 検索する値はmidの右側にあり、leftの値をmidに更新し、midの右側を検索します。

最後に、midの値を更新して次の検索を開始すると同時に、while-else文で見つからない状況を判断し、戻り値を返します。

    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1

ログイン後にコピー

最後に、完全なコードとテストの実行パフォーマンスは次のとおりです。

""" a demo realize binary search"""
 
 
def binary_search(_list, value):
    left = 0   # 列表的起始索引
    right = len(_list)   # 列表的结束索引
    mid = int((left + right)/2)  # 采用此方法，通过四舍五入刚好可以定位到列表的中间位置
    while left < right:
        if _list[mid] == value:
            return mid
        elif _list[mid] > value:
            right = mid
        else:
            left = mid
        mid = int((right + left)/2)
    else:
        return -1
 
 
index = "the index of value in the list: {}"
print(index.format(binary_search([1, 2, 3, 4, 5, 6, 7, 8, 9], 1)))

ログイン後にコピー

実行結果:

Python を使用して二分探索を実装する方法