LeetCode成功药水配对问题：二分查找逻辑错误排查

问题场景 #

我在解决LeetCode「成功药水配对」问题时，思路是先对potions数组排序，再通过二分查找找到第一个满足spell * potion ≥ success的索引，进而计算成功组合的数量。但我的代码无法通过全部测试用例，而另一款思路类似的代码却能通过。同时我有疑问：二分查找中条件判断的顺序会影响结果吗？ 比如将判断条件改为product <= success时，代码也会失败。

我的代码 #

def successfulPairs(spells, potions, success):
    potions.sort()
    result = []
    potion_len = len(potions)
    for s in spells:
        left, right = 0, potion_len - 1
        match_idx = potion_len
        while left <= right:
            mid = (left + right) // 2
            product = s * potions[mid]
            if product >= success:
                match_idx = mid
                right = mid - 1
            else:
                left = mid + 1
        result.append(potion_len - match_idx)
    return result

失败测试用例 #

测试输入：
spells = [10, 20, 30], potions = [1, 2, 3, 4, 5], success = 100
预期输出：[0, 3, 5]
我的代码输出：[0, 2, 4]（错误结果）

正确代码 #

def successfulPairs(spells, potions, success):
    potions.sort()
    result = []
    potion_len = len(potions)
    for s in spells:
        # 用向上取整计算最小满足条件的potion值，避免乘法溢出
        target = (success + s - 1) // s
        left, right = 0, potion_len
        # 左闭右开区间的二分查找
        while left < right:
            mid = (left + right) // 2
            if potions[mid] >= target:
                right = mid
            else:
                left = mid + 1
        result.append(potion_len - left)
    return result

问题分析与疑问解答 #

1. 二分查找的条件判断顺序/逻辑确实会直接影响结果，核心在于你要明确自己的搜索目标：找到「第一个满足spell*potion ≥ success的元素索引」，每一步的条件判断必须对应正确的指针移动逻辑，否则会偏离正确的边界。

2. 你的代码失败的主要原因：

   • 整数溢出问题：当spell和potions[mid]数值较大时，直接相乘会超出部分语言的整数范围（即使Python无溢出限制，极端场景下也可能出现计算异常），导致product值错误，进而干扰条件判断。正确代码通过target = (success + s - 1) // s将乘法转换为向上取整的除法，从根源避免了溢出。
   • 二分边界处理偏差：你将右边界初始化为potion_len - 1，采用的是左闭右闭区间的二分逻辑，但在极端情况（所有元素都满足条件）下，可能会遗漏最左侧的索引。正确代码使用左闭右开区间（右边界为potion_len），更方便处理边界情况。

3. 关于条件改为product <= success后失败的原因：
   当你修改条件时，必须同步调整指针移动逻辑。比如如果要找「最后一个满足product <= success的元素」，那么成功组合数应该是potion_len - (mid + 1)，但如果还是沿用原来的指针移动逻辑（找到满足条件时向左收缩），就会完全偏离目标索引，导致计算出错误的组合数。

内容的提问来源于stack exchange，提问作者Shivam...