二分索引搜索 - 为什么要与 len(a) 进行比较？

Question

所以我想了解二分法。我知道它是一种有用的、节省计算的算法，我知道它做什么以及如何做的一般概念。我没有得到的涉及使用它的搜索功能，取自 https://docs.python.org/2/library/bisect.html

from bisect import bisect_left    

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

有人可以为我详细说明 if 行的 i != len(a) 部分的作用吗？我能读懂它——它检查 x 的插入索引是否等于列表 a 的长度——但我无法理解。为什么有必要？没有它会怎样？

我接着说，假设 x 的插入索引大于 a 的长度，那么 x 显然不存在于 a 中，所以它会喷出错误 - 但如果是这种情况，那么 a[i] == x 无论如何检查它都会跳闸...?

谢谢！

Answer 1

从零开始的索引。 i != len(a) 是为了捕获 i 等于列表长度的确切情况，在这种情况下 a[i] 将引发索引错误（列表从索引 0 开始并上升到len(a) - 1).

Answer 2

因为列表是从 0 索引的，所以 a[i] 对于 i == len(a) 没有意义（最后一个元素的索引是 len(a) - 1）。为这样的 i 执行 a[i] 将抛出 IndexError.

Now if bisect_left(a, x) returns len(a) 那么这意味着应该在列表的末尾 添加元素 以便保留顺序。

另一方面，如果 x 在 a 中匹配，则

bisect_left(a, x) != len(a)

因为If x is already present in a, the insertion point will be before (to the left of) any existing entries。如果它是 before 那么显然插入索引必须小于或等于最后一个索引（因为在最坏的情况下这个 matched 元素将最后索引），最后一个索引是 len(a)-1，它比长度更小。

总而言之，如果bisect_left(a, x) == len(a)那么a中就没有x了。这使我们能够轻松摆脱我在开头提到的“IndexError问题”。

请注意，这（显然）不适用于 bisect_right。然而，按照类似的逻辑，您可以得到类似的结果：如果 bisect_right(a, x) == 0 那么 a 中就没有 x。不幸的是，通过 bisect_right 实现 index 功能会更加困难，因为您仍然需要检查 i == len(a) 以避免 IndexError.

二分索引搜索 - 为什么要与 len(a) 进行比较？

Bisection index search - why compare to len(a)?

python

bisection