Python Bisect - 二分探索
この記事では、Python の組み込みモジュールを使って二分探索を行う方法を見ていきます。bisect モジュールは、関数の根を求めるための二等分法に基づいています。6つの関数から構成されています。bisect()、bisect_left()、bisect_right()、insort()、insort_left()、insort_right() の 6つの関数から構成されています。また、各挿入の後にリストをソートしておくのにも役立ちます。しかし、これらが正しく動作するためには、配列がすでにソートされていることを確認しなければなりません。
bisect.bisect_left() 概要
ソートされたリスト内の数値 x の左端の挿入位置を探すのに使用します。リスト内に x が既に存在する場合は、リスト内のすべての x の中で最も左端の位置に新しい x が挿入されます。
構文
bisect_left(arr, x, lo=0, hi=len(a))
パラメータ
arr |
入力リスト |
x |
挿入位置を指定する要素。 |
lo |
リストのサブセットの開始インデックスを指定するのに役立ちます。デフォルト値は 0 です。 |
hi |
リストのサブセットの終了インデックスを指定するのに役立ちます。デフォルト値は len(arr) です。 |
戻り値
配列を 2つの半分に分割する挿入点を返します：1つ目はすべての値が x よりも小さいもの、2つ目はすべての値が x よりも大きいものです。
bisect_left() のアプリケーション
要素の最初の出現を見つける
from bisect import bisect_left
def binary_search(a, x):
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
else:
return -1
a = [1, 2, 3, 3, 3]
x = int(3)
res = binary_search(a, x)
if res == -1:
print("Element not Found")
else:
print("First occurrence of", x, "is at index", res)
出力：
First occurrence of 3 is at index 2
x より小さい最大値を求める
from bisect import bisect_left
def binary_search(a, x):
i = bisect_left(a, x)
if i:
return i - 1
else:
return -1
# Driver code
a = [1, 2, 4, 4, 8]
x = int(7)
res = binary_search(a, x)
if res == -1:
print("There is no value smaller than", x)
else:
print("Largest value smaller than", x, " is at index", res)
出力：
Largest value smaller than 7 is at index 3
bisect.bisect_right() 概要
ソートされたリスト内の数値 x の右端の挿入位置を返すのに使用します。リスト内に x が既に存在する場合は、リスト内のすべての x のうち最も右端の位置に新しい x が挿入されます。
構文
bisect_right(arr, x, lo=0, hi=len(a))
パラメータ
arr |
入力リスト |
x |
挿入位置を指定する要素。 |
lo |
リストのサブセットの開始インデックスを指定するのに役立ちます。デフォルト値は 0 です。 |
hi |
リストのサブセットの終了インデックスを指定するのに役立ちます。デフォルト値は len(arr) です。 |
戻り値
配列を 2つに分割する挿入点を返します：1つ目はすべての値が <= x の場合、2つ目はすべての値が > x の場合です。
bisect_right() のアプリケーション
要素の最後の出現を見つける
from bisect import bisect_right
def binary_search(a, x):
i = bisect_right(a, x)
if i != len(a) + 1 and a[i - 1] == x:
return i - 1
else:
return -1
a = [1, 2, 4, 4]
x = int(4)
res = binary_search(a, x)
if res == -1:
print(x, "is absent")
else:
print("Last occurrence of", x, "is present at", res)
出力：
Last occurrence of 4 is present at 3
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn