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

[Anonymous]

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

Код: Выделить всё

stacksize = 10000  # default 128 stack
from functools import lru_cache

@lru_cache(stacksize)
def nthfibonacci(n):
if 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 

Подробнее здесь: [url]https://stackoverflow.com/questions/56537382/why-does-pythons-bisect-left-return-a-valid-index-even-if-the-value-does-not-ex[/url]