一尘不染

python中的二进制搜索算法

algorithm

我正在尝试在python中实现二进制搜索,并将其编写如下。但是,无论何时needle_element大于数组中的最大元素,我都无法停止它。

你能帮我吗?谢谢。

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"

阅读 324

收藏
2020-07-28

共1个答案

一尘不染

在的情况下needle_element > array[mid],您当前传递array[mid:]给递归调用。但是您知道它array[mid]太小了,因此您可以array[mid+1:]改为传递(并相应地调整返回的索引)。

如果指针大于数组中的所有元素,则这样做最终将为您提供一个空数组,并且将按预期方式引发错误。

注意:每次创建子阵列都会导致大型阵列的性能下降。最好改为传递数组的边界。

2020-07-28