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:

对于它的值(value)，我通过在您的搜索中添加打印输出以查看发生了什么来解决这个问题。如有疑问，请添加打印输出:

>>> 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 module执行二进制搜索。您不必自己编写，除非您这样做是为了教育值(value)。