二分查找，查找第一个大于目标元素target所对应的下标-2300. 咒语和药水的成功对数

题目链接及描述

2300. 咒语和药水的成功对数 - 力扣（LeetCode）

题目分析

        这道题目作为一个典型的二分查找，题目中所述，找到每一个spells[i]在positions中对应的元素positions[i]使其乘积大于给定元素sucess，并统计每一个spell[i]所对应的positions中所查找元素的个数，并将其返回。

        本题本质思想并不难：

• 对positions数组进行升序排序。【便于二分查找】
• 遍历spells数组，对于每一个spells[i]根据success的值利用除法找到另一个因子num。由于Java中的触发是向下取整的，所以这里需要根据余数是否为0来判断最终因子num是否需要+1操作，否则向下取整算出来的success小于给定success。

  ​​​​​​​long num = ((success % (long)spells[i]) == 0) ? (success / (long)spells[i]) : (success / (long)spells[i] + 1);

• 根据positions数组和num，查找第一个大于等于num的值对应的下标i，并返回i。
• 根据返回的i和positions数组的长度给每一个ans[i]赋值。

        难点分析一：需要将计算出来的num设置为long类型，若设置为int，则强转为int会出现出现精度丢失，通过不了全部测试用例。

        难点分析二：如何根据给定数组positions，查找第一个大于等于目标值target所对应的下标：

1. 给定数组positions中存在大于等于目标值target的元素，则直接返回第一个大于等于目标值target对应的下标。
2. 给定数组positions中不存在大于等于目标值target的元素，此时返回数组长度len，也就是不存在。

        根据以上分析可以定义左边界L=0，右边界R = positions.length。并定义循环while(L < R)。

public int getFirstNum(int[] potions, long target){
        int L = 0, R = potions.length;
        while(L < R){
            int midIdx = (L + R) / 2;
            long mid = (long)potions[midIdx];
            if(mid >= target){
                R = midIdx;
            }else{
                L = midIdx + 1;
            }
        }
        return R; 
}

        关于上面的右边界的定义为什么不将R定义为R = positions.lenth - 1，如果这样定义，由于返回值为L == R，此时对于数组positions中不存在对应目标元素target的情况仍然返回下标len - 1，无法判断数组中存不存在第一个大于等于目标元素traget对应的元素。 

        引申扩展：如何找到数组positions中第一个小于等于目标元素target对应的下标？

    public int getFirstNum(int[] potions, long target){
        int L = -1, R = potions.length - 1;
        while(L < R){
            int midIdx = (L + R) / 2;
            long mid = (long)potions[midIdx];
            if(mid > target){
                R = midIdx - 1;
            }else if(mid <= target){
                L = midIdx;
            }
        }
        return R; 
    }

代码编写

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions);
        int n = spells.length;
        int[] ans = new int[n];
        for(int i = 0; i < n; i++){
            long num = ((success % (long)spells[i]) == 0) ? (success / (long)spells[i]) : (success / (long)spells[i] + 1);
            int res = getFirstNum(potions, num);
            if(res >= 0 && res < potions.length){
                ans[i] = potions.length - res;
            }
        }
        return ans;
    }
    public int getFirstNum(int[] potions, long target){
        int L = 0, R = potions.length;
        while(L < R){
            int midIdx = (L + R) / 2;
            long mid = (long)potions[midIdx];
            if(mid >= target){
                R = midIdx;
            }else{
                L = midIdx + 1;
            }
        }
        return R; 
    }
}