0

晚上好。我正在尝试重新开始编程，并决定在自己的时间做一些练习编码。我目前正在尝试实现二进制搜索，但我的代码中似乎存在一个连续循环。有人可以告诉我发生了什么吗？

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
4

3 回答 3

1

我认为您的问题出在 while 循环的条件下。你有一个“或”而不是一个“和”——这意味着即使你找到了你的结果，newSet>0 条件也会得到满足。

于 2012-10-31T22:11:17.803 回答
1

我怀疑“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()到代码中并单步执行以查找错误。

于 2012-10-31T22:12:57.450 回答
1

您有一些问题，其中一些可以改进：

  • 当元素不在有序列表中时，您需要左右边界索引才能正确执行二进制搜索。在此处查看正确的算法。当您找到您的键或左边界在右边界的右侧或反之亦然 ( max_point < min_point) 时，您将退出 while 循环。
  • 你不需要newSet. 您始终可以在排序列表中使用索引。所以 mid_point 只是一个索引，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
于 2012-11-01T05:47:24.063 回答