2分探索
2分探索 Binary Search
Pythonで2分探索を実装します。
二分探索（にぶんたんさく、英: binary search、BS）やバイナリサーチとは、ソート済み配列に対する探索アルゴリズムの一つ。 出典: フリー百科事典『ウィキペディア（Wikip...
yottagin.com
2019-05-06 23:07
2分探索の練習をします。
重複のないリストの中で、indexの値と数値が等しいものを探します。
例えば、[-13, -2, 0, 3, 5, 10, 12]というリストであれば3、[0, 5, 8, 11, 15, 12]というリストであれば0、[-9, -5, 2, 3, 8, 9]というリストであればNoneが答えになります。
def find_value_equals_index(given_list):
imin = 0
imax = len(given_list) - 1
while imin <= imax:
imid = (imin + imax) // 2
if given_list[imid] < imid:
imin = imid + 1
elif given_list[imid] > imid:
imax = imid - 1
else:
return given_list[imid]
return None