1

所以我试图理解二分法。我知道它是一种有用的、节省计算的算法，我了解了它的作用以及它如何做的一般概念。我没有得到涉及使用它的这个搜索功能，取自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会检查行程无论如何它...？

谢谢！

4

2 回答 2

2

由于列表是从那时开始索引的，0因此对于（最后一个元素具有 index ）a[i]没有意义。这样做会抛出一个.i == len(a)len(a) - 1a[i]iIndexError

现在如果bisect_left(a, x)返回len(a)则意味着该元素应添加到列表的末尾以保持顺序。

另一方面，如果有匹配的xin athen

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. 如果它在之前，那么显然插入索引必须小于或等于最后一个索引（因为在最坏的情况下，这个匹配的元素将具有最后一个索引）并且最后一个索引len(a)-1小于长度。

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

请注意，这（显然）不适用于bisect_right. 但是，按照类似的逻辑，您可以得出类似的结果： if bisect_right(a, x) == 0then there is no xin a. 不幸的是，实现index功能 viabisect_right会更加困难，因为你仍然需要这个检查i == len(a)来避免IndexError.

于 2016-03-29T22:55:51.490 回答
0

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

于 2016-03-29T22:55:32.653 回答