【Python】二分探索を実装する

久しぶりに競技プログラミングの問題を解き始めました．
結構忘れているところもあるので，復習がてらアルゴリズムの実装をメモして行こうと思います．

今回は二分探索です．
普段使う分にはbisectというライブラリを使えば良いのですが(参考)，
今回は一から実装してみたいと思います．
細かいアルゴリズムの解説については，他サイトをご参照ください．(参考

numsをソートされた数字のリスト，targetを探したい数字とし，
その数字が存在する場合はインデックスを返し，存在しない場合は-1を返すようにします．
leftとrightは探索の範囲を表し，これらの大小関係が変わるまで操作を実行します．

def search(self, nums: List[int], target: int) -> int:
    n = len(nums)
    
    left = 0
    right = n - 1

    while left <= right:
        center = (right + left) // 2
        if nums[center] == target:
            return center
        elif nums[center] < target:
            left = center + 1
        else:
            right = center - 1
        
    return -1

参考

• Pythonで二分探索を行うライブラリ「bisect」 - Qiita

• 二分探索(Binary Search)のアルゴリズム | アルゴリズムロジック