【Python_034】アルゴリズム|二分法

このブログではPythonによる二分法を紹介します.アルゴリズムシロはアルゴリズムの研究を始め、二分法から入門したほうがいい.書籍リファレンス:『アルゴリズム図解』
コンセプト
二分検索はアルゴリズムで、入力は秩序化された要素リストです.検索する要素がリストに含まれている場合、二分検索はその位置を返します.そうでなければnullを返します
一般に,n個の要素を含むリストでは,二分検索で最大log 2 nステップ,単純検索で最大nステップが必要である.
コード実装

def binary_search(bucket:list, item:int)->int:
    low = 0
    high = len(bucket)-1
    
    while low<=high:
        mid = (low+high)//2

        guess = bucket[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid+1


bucket = list(range(1,20))
binary_search(bucket,21)
'''
'        '
'''

binary_search(bucket,12)
'''
11
'''