python中的二进制搜索算法

Question

我试图在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"

Answer 1

如同Lasse V.Karlsen在对该问题的评论中提出的那样,与a lower和upper索引合作会好得多.

这将是代码:

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

为什么不使用bisect模块？它应该完成你需要的工作 - 更少的代码供你维护和测试.

Answer 3

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

如果针大于数组中的所有元素,以这种方式执行将最终为您提供一个空数组,并且将按预期引发错误.

注意:每次创建子数组都会导致大型数组的性能下降.最好传入数组的边界.

Answer 4

每次调用它时,array [mid:]都会创建一个新的子副本= slow.你也使用递归,在Python中也是如此.

试试这个:

def binarysearch(sequence, value):
    lo, hi = 0, len(sequence) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if sequence[mid] < value:
            lo = mid + 1
        elif value < sequence[mid]:
            hi = mid - 1
        else:
            return mid
    return None