跟着 Python 库学算法

还没整理完，持续更新中…

changelogs

介绍

最近在用 Python 刷 Leetcode，偶然发现 Python 的一些官方库有许多简洁优雅的算法实现，非常值得学习。于是决定开坑一篇博客，记录一下学习过程。目前计划学习的库有：

bisect：学习二分搜索的最佳实践

bisect 库是 Python 的二分搜索库，bisect名称取自术语二分法的英文–Bisection method。在 cython 仓库的 Lib/bisect.py 提供了一个 Python 的实现。

bisect 库其实有两种实现，在被调用时优先使用 C 语言实现。而当 C 语言实现不可用时，才会使用 Python 实现：

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

上面运用了 Python 社区推荐的 EAFP 范式（Easier to Ask for Forgiveness than Permission），导入了 “fast C implementation”。两种语言的代码逻辑是一致的，这里为了增加学习体验，选择学习 Python 版本的实现。

bisect 库非常的简洁，只有6个接口：bisect_left、bisect_right、insort_left、insort_right、bisect、insort。这些函数的具体用法参阅相关文档，不再赘述。

其中insort* 是对 bisect* 的简单调用，而 bisect 和 insort 只是两个函数（bisect_right、insort_right）的别名。因此，最关键的两个函数就是 bisect_left 和 bisect_right 了。

这两个函数的实现如下：

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.

    A custom key function can be supplied to customize the sort order.
    """

    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.

    A custom key function can be supplied to customize the sort order.
    """

    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_left：找到 【大于等于x的最小值的下标】 。函数名称中的left表示当元素x已经存在于列表中时，结果 i 恰好是在最左侧插入 x 的位置（即第一个 x 的位置）。
• bisect_right：找到 【大于x的最小值的下标】 。函数名称中的right表示当元素x已经存在于列表中时，结果 i 恰好是在最右侧插入 x 的位置（即最后一个 x 的后一个位置）。

不难发现，我们可以从这两份代码中总结出一个通用的二分框架：

while lo < hi:
    mid = (lo + hi) // 2
    if 【mid 满足搜索条件】:
        lo/hi = mid
    else:
        hi/lo = mid - 1, mid + 1

其中：

1. 【mid 满足搜索条件】：其实就是对应于前面加粗的搜索条件。例如对于搜索条件： 【大于等于x的最小值的下标】 ，为 a[mid] >= x。
2. 对于 if 分支：即 mid 满足搜索条件，因为我们要找的是满足条件的最大（小）值，因此设置 lo = mid 或者 hi = mid来缩放区间，注意要包含 mid ！
3. 至于else 分支：显然不包含 mid，为 hi = mid - 1 或者 lo = mid + 1。

Q：你这个通用模板和官方库里的代码也不一样啊？

# Note, the comparison uses "<" to match the
# __lt__() logic in list.sort() and in heapq.

A：是的，官方库的源码与我总结的二分框架其实不完全匹配。这其实是因为如上面的注释所示，为了和其他标准库一致，作者有意使用 __lt__ 魔法函数，即 <来进行比较。这就导致了需要在上面框架的基础上，可能需要交换比较顺序或者取反（并同时交换 if 和 else 块）来"凑"出来 <。但我们在自己手写算法的时候为了方便，可以完全不用遵循这个约束！

对于这个框架，记录一些其他学习过程中的思考笔记：

Q：关于 while 里的条件，bisect 库 lo < hi，有的地方似乎使用的 lo <= hi ？lo和hi的初始值怎么选？

A：

1. 关于while的条件的选择，有的教程里造了各种名词（例如双闭区间法、左闭右开区间法）。这里我建议只使用 lo < hi，这样跳出时：lo == hi，没有额外的心智负担。
2. 至于lo，hi的初始值选取，可以结合搜索条件快速推断，我们的最终目的是为了能够正确表达 数组中的元素均不满足搜索条件这样一个状态。比如对于 bisec 库的条件【大于等于x的最小值的下标】和【大于x的最小值的下标】，可以发现当mid满足条件时，更新hi=mid，不满足时，更新lo=mid+1。因此，若数组中的所有元素均不满足条件时，hi保持不变，而lo会向右移动直到与hi相遇跳出。此时，若将 hi 设置数组长度，那么返回值为数组长度时就表达了数组中的元素均不满足的状态。搜索条件相反时情况类似。如果经常刷题，建议用你喜欢的方式记下这个结论。

Q：官方库作者为什么要选择这两个搜索条件，而不是其他的（例如小于等于 x 的最大值或者小于x的最大值）？这其实涉及到二分搜索很有名的一个坑。

A：如果用小于等于 x 的最大值或者小于x的最大值，正确写法如下：

l, r = 0, len(arr)

while l < r:
    mi = (l + r + 1) // 2 # (*)
    if arr[mi] <= x: l = mi
    else r = mi - 1

注意(*)里面需要+1！不然会遇到死循环，比如 l=1, r=2时，mi = (l + r) // 2值为1，更新l=mi，更新后l和r的值没有变化，搜索函数就永远不会退出！

Q：为什么要统一使用 __lt__?

A：认真想了想，之前遇到过魔改类的 __lt__ 方法实现小根堆变大根堆做法，这里的约束可能是为了照顾类似这种玩法吧，达成某种一致性。

Q：如果数组不是升序怎么办

A：bisect 假设数组为升序，如果数组为降序，除了直接reverse数组，也可以通过 key 参数来解决：

import bisect

arr = [9, 7, 5, 3, 1]
x = 4

index = bisect.bisect_left(arr, -x, key=lambda a: -a)  # 在降序数组中查找插入位置
arr.insert(index, x)  # 在数组中插入元素
print(arr)  # 输出插入后的数组

最后，给一个 bisec 的 CheatSheet，方便在脑海中建立正确的心智模型~

TODO（我研究下用什么软件画图比较好23333）

heapq：如何实现一个堆

总结