python - Python - 二分探索関数を変更する

Question

次のコードを書きました。

def binary_search(key,lst):
    """ iterative binary search
        lst better be sorted for binary search to work"""
    n=len(lst)
    lower=0
    upper=n-1
    outcome=None   # default value
    while lower<=upper:
        middle=(upper+lower)//2
        if key==lst[middle].name:    # item found
            outcome=lst[middle]
            break  # gets out of the loop if key was found
        elif key<lst[middle].name:   # item cannot be in top half
            upper=middle-1
        else:        # item cannot be in bottom half
            lower=middle+1           
    return outcome  

リストを2つではなく3つの部分に分割するように変更しようとしています。つまり、バイナリ検索ではなくなりますが、反復ごとにアルゴリズムがリストを3つのセクションに分割します。

これを実装できませんでした。

どんな助けでも大歓迎です。

Answer 1

リストを 3 つの部分に分割する必要があります。そのためには、upper_middle と lower_middle の 2 つの中間が必要です。if に句を追加する必要があります。下の中央よりも小さい場合は最初の 3 分の 1 で、上の部分よりも高い場合は最後の 3 分の 1 であり、そうでない場合は中央の 3 分の 1 です。

これがプログラミングの良い練習になるとしても、関数の順序が同じ (log n) のままであるため、実際には効率的ではないことに注意してください。