D.二分查找-进阶——2300. 咒语和药水的成功对数

题目链接：2300. 咒语和药水的成功对数（中等）

算法原理：

解法一：暴力枚举（超时）

时间复杂度O(N²)

依次枚举每一个spells和potions的乘积，判断是否符合条件

解法二：二分查找

击败24.90%

时间复杂度O(Nlogn)

枚举每一个spells的同时对potions排序，这样才能够进行二分

那么符合题意的条件就变成了potions[mid]*spells[i]>=success，取的结果是大于等于，故采用“求最左端点”的模板，把所需的mid位置看成右区间的最左端点，如果没有最左端点就是最左端点右侧的值，这样都是能满足条件的

小细节：

①不要用t=(int)(success/spells[i])来作为目标值，因为整数除法会导致判断条件失效

②二分结束后，需要额外判断一下，因为此时left和right都停在了所需mid或者mid的右侧，但如果停在了最后一个位置，恰好最后一个位置的乘积也是<success，那么符合条件的计数就应该是0，而不是1

Java代码：

class Solution { //暴力解法 public int[] successfulPairs(int[] spells, int[] potions, long success) { int n=spells.length; int m=potions.length; int[] pairs=new int[n]; for(int i=0;i<n;i++){ int count=0; for(int x:potions){ long tmp=(long)spells[i]*x; if(tmp>=success) count++; } pairs[i]=count; } return pairs; } }

class Solution { //二分查找优化 public int[] successfulPairs(int[] spells, int[] potions, long success) { int n=spells.length; int m=potions.length; int[] pairs=new int[n]; Arrays.sort(potions); for(int i=0;i<n;i++){ int left=0,right=m-1; while(left<right){ int mid=left+(right-left)/2; if((long)potions[mid]*spells[i]<success) left=mid+1; else right=mid; } pairs[i]=(long)potions[left]*spells[i]>=success?m-left:0; } return pairs; } }