二分查找解题：咒语与药水的成功配对

二分查找

class Solution: def successfulPairs( self, spells: List[int], potions: List[int], success: int ) -> List[int]: ans = [] n = len(potions) potions.sort() for num in spells: left, right = 0, len(potions) while left < right: mid = (left + right) // 2 if num * potions[mid] < success: left = mid + 1 else: right = mid ans.append(n - left) return ans

定义ans列表接收答案，对列表potions排序，通过for循环遍历spells，判断每个咒语能成功的药水数。对中点处乘积判断，若小于success，则left=mid+1（因为索引小于等于mid的都小于success不满足条件），否则right=mid（mid左边的都满足条件）。由此求得满足大于等于success的第一个索引left，n-left即为满足条件的数。例：num = 5left=0，right=5，mid = 2（即3），3*5=15>success=7，执行right = 2，再更新mid = 1.此时left=0，right=2，mid = 1（对应数字为2），2*5=10>success = 7，执行right = 1，更新mid = 0，left = 0不变，更新mid = 0（对应1）1*5=5不满足left = 1，退出循环，即从1开始都满足，个数为n-1=4.依次循环操作。