Почему в python bisect_left возвращает действительный индекс, даже если значение не существует? - PullRequest
Новая
       31

Почему в python bisect_left возвращает действительный индекс, даже если значение не существует?

1 голос
/ 11 июня 2019

Я хочу узнать, существует ли число в отсортированном массиве. Чтобы быть прямым, массив содержит число Фибоначчи от 1 до 63. Ниже приведен генератор чисел Фибоначчи и некоторые его выходные данные. 

stacksize = 10000  # default 128 stack
from functools import lru_cache

@lru_cache(stacksize)
def nthfibonacci(n):
    if n <= 1:
        return 1
    elif n == 2:
        return 1
    elif n > 2:
        return nthfibonacci(n - 2) + nthfibonacci(n - 1)

 output = [nthfibonacci(k) for k in range(1,63+1)]

 # truncated output: [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,987, 
           1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368,.....]

Теперь я хочу узнать, существует число 7 или нет, поэтому я использовал следующий код используя python модуль деления пополам 

from bisect import bisect_left
elem_index = bisect_left(a=output, x=7, lo=0, hi=len(arr) - 1) 
# output of elem_index is  5 ????  . But it is expected to be len(output) +1, right?   
# as we know if element is not found it returns len(array) +1

Опять же, если я просто напишу простой двоичный поиск, он даст мне правильный результат следующим образом: 

def binsearch(arr, key):
    # arr.sort()
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == key:
            return mid
        else:
            if arr[mid] < key:
                low = mid + 1
            else:
                high = mid - 1
    return -1

print(binsearch(arr, 7)) # it gives me -1 as expected

Так что же происходит?

1 Ответ

1 голос
/ 11 июня 2019

Документация по bisect_left объясняет поведение: 

bisect_left(...)
    bisect_left(a, x[, lo[, hi]]) -> index

    Return the index where to insert item x in list a, assuming a is sorted.

Короче говоря, bisect_left (и bisect_right) говоритВы, где находится элемент, если он существует, или куда его вставить, если его нет.

Рассмотрим надуманный пример.Давайте найдем значение в отсортированном списке, когда оно существует. 

l = [1, 4, 5]
bisect.bisect_left(l, 4)
# 1

bisect_left возвращает 1, потому что l[1] равно 4.Теперь повторите процесс, но со значением, которого нет в этом списке. 

bisect.bisect_left(l, 3)
# 1

В этом случае l[1] - это место, где вы найдете 3 , если бы оно существовало вэтот отсортированный список.

Что это значит для вас? Все, что вам нужно сделать, это изменить свою функцию для запроса элемента по индексу, возвращаемому bisect_left, 

def binary_search(items, key):
    idx = bisect_left(items, key)
    if items[idx] != key:
         return -1

    return idx
...