1

我编写了以下代码来对target列表或元组中的值 进行二进制搜索collection。

def binary(collection, target):
    """Binary search
    Takes a sorted list or tuple, collection, then searches for target
    Returns -1 if item isn't found. """
    length = len(collection)
    minimum = 0
    maximum = length - 1
    while minimum <= maximum:
        pivot = (minimum + maximum) // 2
        if collection[pivot] is target:
            return pivot
        elif collection[pivot] > target:
            minimum = pivot + 1
        else:
            maximum = pivot - 1
    return -1

如您所见，当在target中找不到时collection，该函数返回-1。不管我做了什么，函数都返回-1。

>>> test = [1, 2, 3, 4, 5, 6]
>>> binary(test, 5)
-1
>>> binary(test, 1)
-1

是什么导致了这个问题？

4

2 回答 2

4

你有这个条件倒退：

elif collection[pivot] > target:

切换它，搜索工作：

elif collection[pivot] < target:

对于它的价值，我通过在您的搜索中添加打印输出以查看正在发生的事情来解决这个问题。如有疑问，请添加打印输出：

>>> binary([1, 2, 3], 1)
(min=0, max=2, pivot=1)
(min=2, max=2, pivot=2)
     ^ Oops

# After fixing...
>>> binary([1, 2, 3], 1)
(min=0, max=2, pivot=1)
(min=0, max=0, pivot=0)

顺便说一句，内置的bisect 模块执行二进制搜索。你不必自己写，除非你是为了教育价值而写的。

于 2010-09-11T05:22:04.527 回答
1

除了将您的条件测试更正为 之外elif collection[pivot] < target:，您还使用“is”运算符来测试您是否找到了目标项目：

    if collection[pivot] is target:

您应该改用“==”：

    if collection[pivot] == target:

使用 "is" 测试两个事物是否实际上是同一个对象。在 Python 中，小字符串和整数对象通常会被存储和回收，因此这可能有效。但是，在大多数情况下，它不会：

>>> a='abc'
>>> id(a)
2129839392
>>> b='ab'
>>> b+='c'
>>> id(b)
2129963136
>>> a
'abc'
>>> b
'abc'
>>> binary([a],a)
0
>>> binary([a],b)
-1
于 2011-02-16T20:01:12.010 回答