力扣2300.咒语和药水的成功对数（二分法）

 根据 灵茶山艾府 题解所写

题目描述：

给你两个正整数数组 spells 和 potions ，长度分别为 n 和 m ，其中 spells[i] 表示第 i 个咒语的能量强度，potions[j] 表示第 j 瓶药水的能量强度。

同时给你一个整数 success 。一个咒语和药水的能量强度 相乘 如果 大于等于 success ，那么它们视为一对 成功 的组合。

请你返回一个长度为 n 的整数数组 pairs，其中 pairs[i] 是能跟第 i 个咒语成功组合的 药水 数目。

示例 1：

输入：spells = [5,1,3], potions = [1,2,3,4,5], success = 7
输出：[4,0,3]
解释：
- 第 0 个咒语：5 * [1,2,3,4,5] = [5,10,15,20,25] 。总共 4 个成功组合。
- 第 1 个咒语：1 * [1,2,3,4,5] = [1,2,3,4,5] 。总共 0 个成功组合。
- 第 2 个咒语：3 * [1,2,3,4,5] = [3,6,9,12,15] 。总共 3 个成功组合。
所以返回 [4,0,3] 。

示例 2：

输入：spells = [3,1,2], potions = [8,5,8], success = 16
输出：[2,0,2]
解释：
- 第 0 个咒语：3 * [8,5,8] = [24,15,24] 。总共 2 个成功组合。
- 第 1 个咒语：1 * [8,5,8] = [8,5,8] 。总共 0 个成功组合。
- 第 2 个咒语：2 * [8,5,8] = [16,10,16] 。总共 2 个成功组合。
所以返回 [2,0,2] 。

解题思路：

 其中这部分是表示计算一个整数除法的向上取整操作

公式解释

加 b−1 的作用是确保当 a不是 b 的整数倍时，结果会向上取整。

代码实现

class Solution {public int[] successfulPairs(int[] spells, int[] potions, long success) {Arrays.sort(potions);for (int i = 0; i < spells.length; i++) {long target = (success - 1) / spells[i];if (target < potions[potions.length - 1]) { // 防止 long 转成 int 溢出spells[i] = potions.length - upperBound(potions, (int) target);} else {spells[i] = 0;}}return spells;}// 直接二分 long 是 28ms，改成 int 是 26msprivate int upperBound(int[] nums, int target) {int left = -1, right = nums.length; // 开区间 (left, right)while (left + 1 < right) { // 区间不为空// 循环不变量：// nums[left] <= target// nums[right] > target//无符号数右移int mid = (left + right) >>> 1;if (nums[mid] > target) {right = mid; // 二分范围缩小到 (left, mid)} else {left = mid; // 二分范围缩小到 (mid, right)}}return right;}
}