bisect二分查找中key参数的用法

摘要: Python 二分查找

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

二分查找是程序中非常常见的需求。细节和变种比较多，比如整数二分和实数二分；区间二分和值域二分；有重复元素和无重复元素；包含边界和不包含边界等等。有的复杂问题需要画图才能分析清楚。可以自己写二分的代码，当然在 Python 中大部分情况可以用 bisect 模块处理。

bisect 模块实现了一个算法向列表中插入元素，同时保持列表有序。大致是先通过二分查找找到插入位置，然后用 list.insert 方法将元素插入到指定位置。注意 bisect 只有插入和查找，没有删除。

在 Python 3.10 中增加了 key 参数，在计算升序列表 l 中插入元素 x 的插入位置时，l[i] 的值视为 key(l[i]) 进行比较。最后我们用这个特性解决力扣 2300。

有序插入

bisect.insort(l, x) 用于将新元素插入非递减列表，得到的新列表依然是非递减的。其中 l 为列表，x 为待插入的元素。

当有重复元素时，有 insort_left 和 insort_right 两种选择。insort 实际相当于 insort_right。

insort_left(l, x, lo=0, hi=len(l)) 在所需位置插入数据，其中 lo 和 hi 指定了插入的目标区间。若列表的目标区间中已经有了元素 x，则会插入到最左侧位置。

insort_right 的参数和功能基本一样，只是当存在重复元素时，会插入到最右侧位置。

二分查找

bisect.bisect(l, x) 可以在非递减和逆序列表中查找元素，并且也提供了两种返回索引的原则：最左索引还是最右索引。

bisect_left(l, x, lo=0, hi=len(a)) 返回在 l 中插入 x 应该插入的位置，返回索引值。l 是有序序列，可以是列表、元组等可迭代对象。若列表的目标区间中已经有了元素 x，则会返回插入到最左侧的索引。

insort_right 的参数和功能基本一样，只是当存在重复元素时，会返回插入到最右侧的索引。

指定 key 参数 (Python 3.10)

key 参数用于指定一个函数作为 bisect 函数的关键字参数，用于计算列表 l 中每个位置对应的值。

key 是指定了一个单参数的方法，对于每个位置 i，列表中的原始值为 l[i]，使用指定的函数 key(l[i]) 计算出该位置的值，然后将其作为该位置的值作为与 x 比较值。

题目：2300. 咒语和药水的成功对数

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

提示：

n == spells.length
m == potions.length
1 <= n, m <= 1e5
1 <= spells[i], potions[i] <= 1e5
1 <= success <= 1e10

示例 1：
输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：

• 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
• 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
• 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
  所以返回 [4,0,3] 。

示例 2：
输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：

• 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
• 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
• 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
  所以返回 [2,0,2] 。

算法：二分

将 potions 升序排序。然后依次枚举 spells 中的每个值 s，我们要在升序列表 potions 中查找出最左的位置 p，使得当 $j \geq p$ 时 有 $s \cdot potions[j] \geq success$。此时 result[i] = m - p。

代码 (Python)

对于 potions 中的每个元素 potions[j]，将其视为 func(potions[j])，其中 func(x) = s * x。然后寻找大于等于 success 的最小索引。

import bisect

def func(s):
    def _func(x: int) -> int:
        return x * s
    return _func

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n = len(spells)
        m = len(potions)
        potions.sort()
        result = [0 for _ in range(n)]
        for i, s in enumerate(spells):
            myfunc = func(s)
            k = bisect_left(potions, success, key=myfunc)
            result[i] = m - k
        return result

---