python中的二进制搜索算法

Question

我试图用python实现二进制搜索，并编写如下。但是，每当针元素大于数组中最大的元素时，我无法使其停止。

你能帮忙吗？谢谢。

def binary_search(array, needle_element):
    mid = (len(array)) / 2
    if not len(array):
        raise "Error"
    if needle_element == array[mid]:
        return mid
    elif needle_element > array[mid]:
        return mid + binary_search(array[mid:],needle_element)
    elif needle_element < array[mid]:
        return binary_search(array[:mid],needle_element)
    else:
        raise "Error"

Answer 1

使用lower和upper索引会更好，因为Lasse V.Karlsen在对这个问题的评论中建议使用。

这就是代码：

def binary_search(array, target):
    lower = 0
    upper = len(array)
    while lower < upper:   # use < instead of <=
        x = lower + (upper - lower) // 2
        val = array[x]
        if target == val:
            return x
        elif target > val:
            if lower == x:   # these two are the actual lines
                break        # you're looking for
            lower = x
        elif target < val:
            upper = x

• lower < upper到达较小的数字（从左侧）后将停止
• if lower == x: break到达较高的数字（从右侧）后将停止

示例：

>>> binary_search([1,5,8,10], 5)   # return 1
1
>>> binary_search([1,5,8,10], 0)   # return None
>>> binary_search([1,5,8,10], 15)  # return None

Answer 2

在needle_element > array[mid]的情况下，当前将array[mid:]传递给递归调用。但是你知道array[mid]太小了，所以你可以通过array[mid+1:]（并相应地调整返回的索引）。

如果指针比数组中的所有元素都大，这样做最终会得到一个空数组，并且会像预期的那样产生错误。

注意：每次创建子数组都会导致大型数组的性能下降。最好是在数组的边界中传递。

Answer 3

为什么不使用对分模块呢？它应该完成你所需要的工作——更少的代码供你维护和测试。