バイナリナビゲーション

1010 ワード
アルゴリズム#アルゴリズム# テキストリンク

1.概念

  • (仮定)所与のdata setは、整列されたデータでなければならない.
  • ルックアップ値をdata setの中間値と比較します.
  • 検索する値がdata setの中間値より大きい場合、data setの中間値以上の新しいデータセットで値を検索します.
    • 手順
  • 2を繰り返します.
  • の値が見つかったらTrueを返します.

    • 2.コード

    def binary_search(data, search):
    print(data)
    if len(data) == 1 and data[0] == search:
        return True
    if len(data) == 1 and data[0] != search:
        return False
    if len(data) == 0:
        return False
    
    medium = len(data) // 2
    
    if data[medium] == search:
        return True
        
    else:
        if search > data[medium]:
            return binary_search(data[medium:], search)
        else:
            return binary_search(data[:medium], search)

    3.時間複雑度


    n個のリストをk回比較し,毎回2を1で割った.
    n x 1/2 x 1/2 ... = 1
    nx(1/2のk平方)=1
    n=2のk二乗
    k = logn
    bigoマーキング法を用いて,k+1は最終時間複雑度,最終的にO(logn)であった.
    白駿2293硬貨
    白駿10845:Q