Python 二分查找总是返回目标未找到值

Question

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

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

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

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

是什么导致了这个问题？

Answer 1

你有这样的条件：

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 模块执行二分搜索。您不必自己编写，除非您这样做是为了教育价值。

Answer 2

除了将条件测试更正为 elif collection[pivot] 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