二进制搜索算法的实现

Question

我使用这个二进制搜索函数得到一个较大数据集的索引错误。当我输入一个较小的数据集时，即[1,2,3,4,5]搜索5。算法按预期运行。但是，当我获取下面的文本时，使用空参数列表（delimeter char为“”）调用string对象的split方法，并将字符串拆分为列表值，其中每个元素都是字符串，然后搜索单词“culpa”，我最终会出现以下错误：

索引错误：列表索引超出范围

非常感谢你的帮助。非常感谢。

字符串：1。知识产权是一种权利，是一种精英的权利，是劳动和财富的暂时性权利。但是，在最低限度上，我们需要一个实验室来进行日常工作。两人或两人在一个无教区的房间里互相指责。除偶尔因疏忽而死亡外，不得因疏忽而导致动物死亡。

代码：http://ideone.com/TXVfQA

def binary_search(l,skey,start,stop):
    length = (stop - start) + 1 # length of search space
    middle = start + (length / 2)
    mid_val = l[middle]
    if skey == mid_val:
        return middle
    elif skey > middle:
        return binary_search(l,skey,(middle + 1),stop)
    else:
        return binary_search(l,skey,start,(middle - 1))

Answer 1

您从不检查stop是否小于start。递归调用将很容易创建该条件。

Answer 2

这个算法有几个问题。

首先，如果您请求的项目小于列表中最小的（skey）

对于列表中未显示元素的情况，您并没有适当的行为。例如，如果未找到元素，则可以返回None。您的代码可以这样修复：

def binary_search(l, skey, start, stop):
    # possible answer is always in interval [start, stop)
    while start + 1 != stop:
        middle = (start + stop) // 2
        mid_val = l[middle]
        if skey < mid_val:
            stop = middle
        else:
            start = middle
    return start if l[start] == skey else None

它将发现元素的最后一次出现等于skey。它还使用循环而不是递归，从而节省了执行函数所需的时间。