Python 中 bisect_left 中的索引超出范围 3

Question

我正在编写这段代码，其中我使用了 bisect 模块中的 bisect_left 函数，它是 Python 的第一方模块。我仅将它与两个参数一起使用，即 sorted_list 和目标（我必须为其找到合适的索引值的那个）。

问题是：如果我的目标大于最低值和最高值的总和，函数将返回 index = len(sorted_li)，因此出现索引错误。我可以使用 try 和 except，但除此之外，我很想知道它为什么会这样。

以下是我的代码：

from bisect import bisect_left

li = [10,15,3,6,10]
k  = 19

def binary_search(sorted_list,target):

    index = bisect_left(sorted_list,target)

    print(index)

    if sorted_list[index] == target:
        return index

    else:
        return False

def function(sorted_li,k):

    """
    Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
    For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
    """

    print(sorted_li)

    for i in range(len(sorted_li)):

        print('Next iteration')

        print(sorted_li[i])

        target = k - sorted_li[i]

        j = binary_search(sorted_li,target)

        if j:
            if j != i:
                print(sorted_li[i])
                print(sorted_li[j])
                return True
            else:
                if j + 1 < len(sorted_li):
                    if sorted_li[j+1] == target:
                        print(sorted_li[i])
                        print(sorted_li[j+1])
                        return True
                if j - 1 > 0:
                    if sorted_li[j-1] == target:
                        print(sorted_li[i])
                        print(sorted_li[j-1])
                        return True
    return False


if __name__ == "__main__":

    li.sort()
    a = function(li,k)
    print(a)

输出结果如下：

但是当我将 k 更改为 18 时，代码运行正常，输出如下：

我已经尝试过使用不同的数字集来实现相同的结果。输出保持不变。

Answer 1

您正在使用 bisect_left，它有下一个目的：它在 a 中寻找 x（在您的情况下是目标）的插入点以保持排序。

因此，对于您的情况，当您第一次 binary_search 第一次调用 16 (19 - 3) 时，它会使用二进制算法将您的号码与 li 列表中的项目进行比较，然后它 return 插入 5 的位置，因为在您的列表 [3, 6, 10, 10, 15] 中，插入点应该在 15 之后，这是正确的。

如果打开documentation you can find next method in searching sorted list

这正是您所需要的，它会搜索列表中的确切项目和它的 return 位置（如果它存在）或者引发 ValueError 因为找不到项目。

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

Python 中 bisect_left 中的索引超出范围 3

Index going out of range in bisect_left in Python 3

binary-search

python-3.x