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

Question

我写了下面的代码，用来在一个列表或元组中进行二分查找，查找的值是 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

你可以看到，当在 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: 之外，你还用了 "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

Answer 2

你把这个条件搞反了：

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)

对了，Python里有一个内置的bisect模块可以进行二分搜索。你不需要自己写一个，除非你是为了学习的目的。