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  

我正在尝试更改它以使其将列表分为 3 个部分而不是 2 个部分。我的意思是它不再是二进制搜索，但对于每次迭代，算法会将列表分为 3 个部分。

我无法实现这一点。

任何帮助将不胜感激。

Answer 1

您需要将列表分为 3 个部分，为此您需要两个中间部分：upper_middle 和 lower_middle。您需要在 if 中添加更多子句。如果它小于下中间，那么它是前三分之一，如果它高于上三分之一，它是最后三分之一，否则，它在中间三分之一。

请记住，即使这是一个很好的编程练习，它并没有真正提高效率，因为函数的顺序保持不变（log n）。