[python刷题模板] 二分模板

一、 算法&数据结构

1. 描述

python3中提供了bisect.bisect_left()和bisect.bisect_right()函数使用，但是只有python3.10及以上才支持key参数。
因此自己模仿stl写一个python实现。

• 有的题从题干条件推答案非常难。这时反过来思考，如果知道答案，反过来计算题干中的条件反而很简单。
• 这时可以枚举答案，看看哪个答案推出的条件正好是题干给出的那个。
• 如果暴力枚举会炸，用二分就能从O(n)降到O(lgn)。
• 用二分的条件是f(x)相对于x是单调的。单调递增或递减都可以，相应的调整二分方向即可。

2. 复杂度分析

1. 查询query, O(log₂n)

3. 常见应用

1. 计算开方。

4. 常用优化

1. python的bisect_left非常好用，但是只支持单调递增的；如果我们的目标函数是单调递减的，这时可以调整key和x的正负性来变相使用这个方法。

二、 模板代码

1. my_bisect_left(a, x, lo=None, hi=None, key=None):返回数组a中第一个大于等于x的位置

def my_bisect_left(a, x, lo=None, hi=None, key=None):
    """
    由于3.10才能用key参数，因此自己实现一个。
    :param a: 需要二分的数据
    :param x: 查找的值
    :param lo: 左边界
    :param hi: 右边界(闭区间)
    :param key: 数组a中的值会依次执行key方法，
    :return: 第一个大于等于x的下标位置
    """
    if not lo:
        lo = 0
    if not hi:
        hi = len(a) - 1
    else:
        hi = min(hi, len(a) - 1)
    size = hi - lo + 1

    if not key:
        key = lambda _x: _x
    while size:
        half = size >> 1
        mid = lo + half
        if key(a[mid]) < x:
            lo = mid + 1
            size = size - half - 1
        else:
            size = half
    return lo


def my_bisect_right(a, x, lo=None, hi=None, key=None):
    if not lo:
        lo = 0
    if not hi:
        hi = len(a) - 1
    else:
        hi = min(hi, len(a) - 1)
    size = hi - lo + 1

    if not key:
        key = lambda _x: _x
    while size:
        half = size >> 1
        mid = lo + half
        if key(a[mid]) > x:
            size = half
        else:
            lo = mid + 1
            size = size - half - 1
    return lo

2. my_bisect_right(a, x, lo=None, hi=None, key=None):返回数组中第一个大于x的位置

代码上边有。

def my_bisect_right(a, x, lo=None, hi=None, key=None):
    if not lo:
        lo = 0
    if not hi:
        hi = len(a) - 1
    else:
        hi = min(hi, len(a) - 1)
    size = hi - lo + 1

    if not key:
        key = lambda _x: _x
    while size:
        half = size >> 1
        mid = lo + half
        if key(a[mid]) > x:
            size = half
        else:
            lo = mid + 1
            size = size - half - 1
    return lo

三、其他

1. 补充

四、更多例题

• 待补充

五、参考链接

• 待补充