python - 为什么即使值不存在，python 的 bisect_left 也会返回有效索引？

Question

我想查找一个数字是否存在于已排序的数组中。简单来说，数组包含从 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 bisection module :

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

那么发生了什么？

Answer 1

如前所述，bisect_left()只是定位列表中元素的插入点以维持排序顺序。该文档还shows如何将 bisect_* 函数转换为实际查找，以便您可以使用:

def index(lst, elem):
    i = bisect_left(lst, elem)
    if i != len(lst) and lst[i] == elem:
        return i
    return -1