python二分検索の2つの実装方法(非再帰実装、再帰実装)

二分検索は半分検索と呼ばれ、利点は回数が少なく、検索速度が速く、平均性能が良いことである.その欠点は,調査対象テーブルが整列テーブルであり,プラグイン削除が困難であることである.
したがって,折半ルックアップ方式は,頻繁に変動しないシーケンステーブルに適している.
1.12216;まず、表の要素が昇順に並べられていると仮定し、表の中間位置に記録されたキーワードを検索キーワード⽐と比較し、両者が等しい場合、検索に成功する.2.そうでなければ、中間位置記録を利用して表を前、後の2つの⼦表に分け、中間位置記録のキーワードが検索キーワードより大きい場合は、前の1つの⼦表を1ステップ検索し、そうでなければ後の1つの⼦表を1ステップ検索する.3.検索が成功するまで、またはテーブルが存在しないまで、検索が成功しないまで、上記の手順を繰り返します.
方法一:非再帰的実現

def binary_search(list1, item):
    start = 0
    end = len(list1) - 1
    while start <= end:
        mid = (start + end) // 2
        if list1[mid] == item:
            return True
        elif item < list1[mid]:
            end = mid - 1
        else:
            start = mid + 1
    return False


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binary_search(testlist, 3))
print(binary_search(testlist, 13))

方法2:再帰的に実現する

def binary_search2(list1, item):
    if len(list1) == 0:
        return False
    else:
        mid = len(list1) // 2
        if list1[mid] == item:
            return True
        else:
            if item < list1[mid]:
                return binary_search2(list1[:mid], item)
            else:
                return binary_search2(list1[mid + 1:], item)


testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42]
print(binary_search2(testlist, 3))
print(binary_search2(testlist, 13))