【備忘録】二分探索

あくまで備忘録なんで雑に記録します

検索対象に何を持ってくるか？
左端と右端をlowとhighに指定
①完全一致
②曖昧一致
サンプル

検索対象に何を持ってくるか？

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)