Бинарный поиск 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

Как вы можете видеть, когда target не найден в collection, функция возвращает -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] < 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