二分查找函数

Question

晚上好。我正试图重新开始编程，并决定在自己的时间里做一些编程练习。我目前正在尝试实现二进制搜索，但在我的代码中似乎有一个连续的循环。有人能给我一点提示吗?这是怎么回事？

def binChop(key, ordered_set):

    found = False
    newSet = ordered_set

    while found != True or newSet > 0:
        midpoint = int(len(newSet)/2)
        if key < newSet[midpoint]:
            found = False
            newSet = newSet[:midpoint]
        elif key > newSet[midpoint]:
            found = False
            newSet = newSet[midpoint:]
        elif key==newSet[midpoint]:
            found = True
    return found

Answer 1

我认为您的问题出在while循环的条件下。你有一个'or‘而不是一个'and’-这意味着即使你找到了你的结果，newSet>0条件也会得到满足。

Answer 2

我怀疑"newSet > 0“总是正确的。如果它是一个标准的python集，你会得到一个错误：

>>> b=set()
>>> b
set([])
>>> b > 0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: can only compare to a set

但既然你没有，我猜它是一个列表或元组：

>>> a=[]
>>> a > 0
True
>>> b=()
>>> b > 0
True

这两者都没有做你期望的事情(检查长度)。

通常，将import pdb; pdb.set_trace()添加到代码中并逐步执行以查找错误。

Answer 3

您有一些问题和一些可以改进的问题：

• 当元素不在有序列表中时，需要左边界索引和右边界索引才能正确执行二进制搜索。请参阅正确的算法here。当你找到你的键或者左边界在右边界的右边时，或者反之亦然，你就离开了while循环，(max_point < min_point).
• You不需要newSet。您始终可以在排序列表中使用索引。因此键只是一个索引，min_point (左边界)和max_point (右边界)也是如此。
• 二进制搜索通常返回键的索引作为返回值。如果未找到，则返回-1.

我的python代码如下所示：

def binChop(key, ordered_list):

    min_point, max_point = 0, len(ordered_list)-1

    while min_point <= max_point:
        mid_point = (min_point+max_point)/2

        if ordered_list[mid_point] < key:
            min_point += 1
        elif ordered_list[mid_point] > key:
            max_point -= 1
        else:
            return mid_point
    return -1

test_cases = [[], [5], [4,5], [5,6], [1,5,6], [1], [1,4], [1,6,15]]
for ordered_list in test_cases:
    print "%-10s %5s" % (ordered_list, binChop(5, ordered_list))

Outputs:
list       index of 5
[]            -1
[5]            0
[4, 5]         1
[5, 6]         0
[1, 5, 6]      1
[1]           -1
[1, 4]        -1
[1, 6, 15]    -1