python - Python 2 变量中的二进制搜索未更新导致无限循环.....为什么变量未更新？

Question

这是我的二分搜索。mid 不会更新，它会无限循环。

def binary_search (z, A, start, end):
    if len(A) == 0:
        return None
    else:
        mid = start + (end - start) / 2
        if (z < A[mid]) and (z > A[mid-1]):
            return A[mid-1]
        elif (z < A[mid]):
            return binary_search(z, A, start, mid)
        elif (z > A[mid]):
            return binary_search(z, A, mid, end)

Answer 1

def binary_search (z, A, start, end):
    if end < start:
        return None
    else:
        mid = start + (end - start) / 2
        if (z < A[mid]):
            return binary_search(z, A, start, mid-1)
        elif (z > A[mid]):
            return binary_search(z, A, mid+1, end)
        else: 
            return mid

我改变了几件事。

我首先检查更改end < start:，因为if len(A) == 0:它将保持不变并且不允许您将其用作基本案例。

此外，当您返回二进制搜索时，您需要跳过中间值，因为那是您要返回的值。

我测试了代码，它可以工作！