2分探索
2分探索 Binary Search
Pythonで2分探索を実装します。
二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。 出典: フリー百科事典『ウィキペディア（Wikip...
yottagin.com
2019-05-06 23:07
2分探索の練習です。
2分探索を使って、リストの中で目標に最も近い値を探します。
例えば、 [1, 3, 5, 6, 6, 8, 9, 11, 15, 16] というリストがあって目標が14だとすると、一番近い値は近い値は15になります。
def binary_search_find_closest(data, target):
if len(data) == 0:
return None
if len(data) == 1:
return data[0]
min_diff = float('inf')
imin = 0
imax = len(data) - 1
closest_num = None
while imin <= imax:
imid = imin + (imax - imin) // 2
# 中心の左右の値と目標との差を計算する。
if imid + 1 < len(data):
min_diff_right = abs(data[imid+1] - target)
if imid > 0:
min_diff_left = abs(data[imid-1] - target)
# 最初の差と最も最小に近い値を更新する。
if min_diff_left < min_diff:
min_diff = min_diff_left
closest_num = data[imid-1]
if min_diff_right < min_diff:
min_diff = min_diff_right
closest_num = data[imid+1]
# 2分探索する。
if data[imid] < target:
imin = imid + 1
elif data[imid] > target:
imax = imid -1
else:
return data[imid]
return closest_num
list_given = [1, 3, 5, 6, 6, 8, 9, 11, 15, 16]
# 15が表示される。
print(binary_search_find_closest(list_given, 14))