二分查找算法的实现

Question

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

IndexError :列表索引超出范围

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

弦: 1. Lorem ipsum dolor坐着，敬请光临，sed do eiusmod tempor incididunt labore et dolore aliqua。从现在到现在，我的工作一直都是这样的。我不是在谴责它，而是在无意义的地方逃亡。除了偶尔不提供证据的情况外，不能在我的办公室里犯下过错。

代码：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

这个算法有几个问题。

首先，如果您请求的项小于列表中的最小项(skey < l[start])，则它会循环。其次，当为skey not in l[start:stop]时，搜索会超出索引范围。

对于元素不在列表中显示的情况，您没有适当的行为。例如，如果找不到元素，则返回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的元素。它还使用循环而不是递归，节省了执行函数所需的时间。

Answer 2

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