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

Question

我想找出排序数组中是否存在一个数字。为了保持直线，数组包含从1到63的fibonaccci数。下面是斐波纳契数发生器和它的一些输出。在

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号是否存在，所以我使用了下面的代码 使用pythonbisection module

^{pr2}$

同样，如果我只写一个简单的二进制搜索，它会给出正确的结果，如下所示：

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

The documentation on ^{}解释行为：

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。现在，重复这个过程，但是使用一个不在该列表中的值。在

^{pr2}$

在本例中，l[1]是在排序列表中存在的3。在

---

这对你意味着什么？您所要做的就是修改函数以查询bisect_left返回的索引处的元素

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

    return idx