二分探索 メモ

二分探索のメモ

.py

def index(arr:list,value:int,exactry:bool=True,ceil:bool=False):
    #ソート済配列をもらって二分探索したうえでインデックスを返す関数。二分探索をします。
    #(必須)第1引数にソート済みの配列、第2引数に探したい値を入れる。
    #(任意,デフォルト)exatry=Trueでその値がドンピシャの時にのみインデックスを返す。なかった場合は-1を返す。
    #この時、値が複数個ある場合はceilルール通りにインデックスを返す。(ceil=Trueの時は一番右側を返し、ceil=Falseの時は一番左側を返す)
    #(任意)exatry=Falseでその値がなくてもceilのルール通りにインデックスを返す。
    #(任意,デフォルト)ceil=Falseでその値より小さい一番大きい値のインデックスを返す。
    #(任意)ceil=Trueでその値より大きい一番小さい値のインデックスを返す。
    left, right = 0, len(arr) - 1
    result = -1
    while left <= right:
        center = (left + right) // 2
        if arr[center] == value:
            result = center
            if ceil:
                left = center + 1  # 右側に同じ値がないかを確認
            else:
                right = center - 1  # 左側に同じ値がないかを確認
        elif arr[center] < value:
            left = center + 1
        else:
            right = center - 1
    if result != -1:
        return result
    if exactry:
        return -1
    if ceil:
        return right if 0 <= right else -1
    else:
        return left if left < len(arr) else -1