通过 Python 源码分析二分查找落点问题

对有序数据来说，二分查找是一种简单高效的搜索方法。但即使在各种各样的背景下写过许多次的二分查找算法，二分查找的落点问题仍然常常让我感到困惑。举例来说，所谓二分查找的落点问题，就是在一个升序序列中，所查找的下标应当在目标元素的最左边还是最右边。仅需要改变 if 判断语句的一个等号结果就会大不相同。

实际上网络上已经有许多详尽的解释和参考教程解释如何在编写二分查找时精确掌控其落点。但我认为如果要加深印象，以标准库里的源码作为例子能更深入了解二分查找的基本原理。

bisect 库

关于二分查找/二分插入的 Python 官方库是 bisect，其源码位于 Github 上。

bisect 库默认输入序列是升序的

在 bisect 库中，二分插入实际上是二分查找的封装。因此以下将着重分析右落点二分查找 bisect_right 和左落点二分查找 bisect_left 。

以下的例子体现了两种函数的不同：

bisect 库两种二分查找的区别

二分查找源码

源码如下：

def bisect_right(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(i, x) will
    insert just after the rightmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < a[mid]:
                hi = mid
            else:
                lo = mid + 1
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if x < key(a[mid]):
                hi = mid
            else:
                lo = mid + 1
    return lo


def bisect_left(a, x, lo=0, hi=None, *, key=None):
    """Return the index where to insert item x in list a, assuming a is sorted.
    The return value i is such that all e in a[:i] have e < x, and all e in
    a[i:] have e >= x.  So if x already appears in the list, a.insert(i, x) will
    insert just before the leftmost x already there.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    # Note, the comparison uses "<" to match the
    # __lt__() logic in list.sort() and in heapq.
    if key is None:
        while lo < hi:
            mid = (lo + hi) // 2
            if a[mid] < x:
                lo = mid + 1
            else:
                hi = mid
    else:
        while lo < hi:
            mid = (lo + hi) // 2
            if key(a[mid]) < x:
                lo = mid + 1
            else:
                hi = mid
    return lo

为何二分查找的左右落点不同

观察源码能发现，两个函数的主要差距在如下部分：

# bisect_right
if x < a[mid]:                
    hi = mid            
else:                
    lo = mid + 1

# bisect_left
if a[mid] < x:
    lo = mid + 1
else:
    hi = mid

实际上二者的差异就在于，当 a[mid] == x 时，应当向高半区迭代还是向低半区迭代。

对于希望落点在目标元素右侧的二分查找，当 a[mid] == x 时，应当向它的右侧查找，即 lo = mid + 1 。这意味着接下来的二分查找需要向比 x 更大的那些数迭代，这样就能保证 x 一定在最后结果的前面。注意到由于 + 1的缘故，查找结果并不是在最后一个目标元素上，而是指向它后一个元素。
类似的，对于希望落点在目标元素左侧的二分查找，当 a[mid] == x 时，应当向它的左侧查找，即 hi = mid 。这意味着接下来的二分查找需要向比 x 更小的那些数迭代，这样就能保证 x 一定在最后结果的后面