Pythonでバイナリサーチ(二分探索)
Pythonでバイナリサーチを行うサンプルを作ってみました。
まずバイナリサーチの本体です。
def binary_search(numbers, goal, ix_top, ix_bottom):
if ix_top > ix_bottom:
return - 1
ix_this = int((ix_top + ix_bottom) / 2)
x = numbers[ix_this]
if x == goal:
return ix_this
elif goal < x:
return binary_search(numbers, goal, ix_top, ix_this - 1)
else:
return binary_search(numbers, goal, ix_this + 1, ix_bottom)
if ix_top > ix_bottom:
return - 1
ix_this = int((ix_top + ix_bottom) / 2)
x = numbers[ix_this]
if x == goal:
return ix_this
elif goal < x:
return binary_search(numbers, goal, ix_top, ix_this - 1)
else:
return binary_search(numbers, goal, ix_this + 1, ix_bottom)
次に使用例です。
numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
goal = 5
ix_top = 0
ix_bottom = len(numbers) - 1
index = binary_search(numbers, goal, ix_top, ix_bottom)
print(index)
goal = 5
ix_top = 0
ix_bottom = len(numbers) - 1
index = binary_search(numbers, goal, ix_top, ix_bottom)
print(index)
[ 2021年7月10日 | カテゴリー: Python, デジタル | タグ: アルゴリズム ]
« 人口あたり感染者数の多い都道府県 | Pythonのtkinterを使ってみる »
コメントを残す