Python での二分探索
Harshit Jindal
2023年1月30日
注意
二分探索について詳しく理解したい場合は、二分探索アルゴリズムの記事を参照してください。
二分探索アルゴリズム
ここでは、n の要素を含むソートされていない配列 A[] があると仮定して、要素 X を見つけたいとします。
-
loを0とし、hiをn - 1とします。 -
lo<hiの場合、mid=lo + (hi - lo)/2とします。A[mid]==Xの場合、要素が見つかったのでインデックスmidを返します。A[mid]<Xの場合、左半分の要素を破棄してloをmid+1とします。- そうでない場合、
A[mid]>Xの場合は、右半分の要素を破棄し、hiをmid-1とします。
-
要素が見つからないので
-1を返します。
二分探索のための Python プログラム
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 1, 5]
x = 4
n = len(arr)
result = binary_search(arr, x, n)
if result == -1:
print("Element not found")
else:
print("Element is present at index", str(result))
出力：
Element is present at index 2
著者： Harshit Jindal
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