あくまで備忘録なんで雑に記録します検索対象に何を持ってくるか？
IndexNumでやる（インデックスナンバー）※要素が複数あると、rightなら先頭の要素、leftなら末尾の要素、のインデックスを返す
return をhighやlowやm
要素→indexは遅いのに、「要素をバイナリサーチ」をdef化してindexを組み込んでしまった失敗あり
左端と右端をlowとhighに指定
（low = -1 / high = n+1 とかにして失敗あり、out of range）
low = 0 / high = len(List)-1 に合わせる
①完全一致
whileで、追い越しまで続けるright – left > 0（left:1 m:1 high:2で終了すると4が検索できない）
if x == mで return m
elif mより上？or下？ high = m-1 (low = m+1)を繰り返し、
抜けたら return 無かったです
②曖昧一致
whileで、最後の隣同士 high – low > 1で終了（left:1 m:1 high:2）
（隣同士で終わらないと永遠に続く（例x=9））
if mより上？or下？ high = m (low = m)を繰り返し、
抜けたら return high(low)
サンプル
#完全一致
def binary_search(numbers, value):
left, right = 0, len(numbers) - 1
while right - left > 0:
mid = (left + right) // 2
if numbers[mid] == value:
return mid
elif numbers[mid] < value:
left = mid + 1
else:
right = mid - 1
return "無かったです"#あいまい
def binary_search(numbers, value):
left, right = 0, len(numbers) - 1
while right - left > 1:
mid = (left + right) // 2
if numbers[mid] < value:
left = mid
else:
right = mid
return right
#A = [2, 3, 3, 4, 4, 5]で4をサーチ(return right)-->3
#A = [2, 3, 3, 4, 4, 5]で4をサーチ(return left)-->2#再帰
def binary_search(numbers, value):
def _binary_search(numbers, value, left, right):
if left > right:
return -1
mid = (left + right) // 2
if numbers[mid] == value:
return mid
elif numbers[mid] < value:
return _binary_search(numbers, value, mid + 1, right)
else:
return _binary_search(numbers, value, left, mid - 1)
return _binary_search(numbers, value, 0, len(numbers) - 1)
コメント