python - 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

使用 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