本文主要是介绍二分查找，查找第一个大于目标元素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所对应的下标：
- 给定数组positions中存在大于等于目标值target的元素，则直接返回第一个大于等于目标值target对应的下标。
- 给定数组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; }
}这篇关于二分查找，查找第一个大于目标元素target所对应的下标-2300. 咒语和药水的成功对数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
