[Java恶补day24] 整理模板·考点三【二分查找】

考点三【二分查找】

【考点总结】

1. 二分查找模板：红蓝染色法

！！！习惯用开就用开，习惯用闭就用闭！！！

（核心）：对于区间左右端点更新，若左/右端点是开区间，就没有-1 +1；若左/右端点是闭区间，有-1 +1。
（溢出）：对于部分语言，存在mid的溢出问题，修改方式：int mid = low + (high - low) / 2;，这里的/2是针对(high-low)的！

①闭区间[low, high]

//定义区间左右端点
int low = 0;
int high = n - 1;
//左端点在右端点右侧（区间为空），就退出循环
while (low <= high) {
	//定义中位数
    int mid = (low + high) / 2;
    //判断
    if (nums[mid] == target) {
    	// TODO 返回目标值 或 返回true 或 其他操作
    } else if (nums[mid] >= target) {
	    high = mid - 1;
    } else {
    	low = mid + 1;
    }
}
// TODO 返回false 或 其他操作

②开区间(low, high)

//定义区间左右端点
int low = -1;
int high = n;
//左端点在右端点前一个位置（区间为空），就退出循环
while (low + 1 < high) {
	//定义中位数
    int mid = (low + high) / 2;
    //判断
    if (nums[mid] == target) {
    	// TODO 返回目标值 或 返回true 或 其他操作
    } else if (nums[mid] >= target) {
	    high = mid;
    } else {
    	low = mid;
    }
}
// TODO 返回false 或 其他操作

③左开右闭区间(low, high]

//定义区间左右端点
int low = -1;
int high = n - 1;
//左端点、右端点重合（区间为空），就退出循环
while (low < high) {
	//定义中位数
    int mid = (low + high) / 2;
    //判断
    if (nums[mid] == target) {
    	// TODO 返回目标值 或 返回true 或 其他操作
    } else if (nums[mid] >= target) {
	    high = mid - 1;
    } else {
    	low = mid;
    }
}

④左闭右开区间[low, high)

//定义区间左右端点
int low = 0;
int high = n;
//左端点、右端点重合（区间为空），就退出循环
while (low < high) {
	//定义中位数
    int mid = (low + high) / 2;
    //判断
    if (nums[mid] == target) {
    	// TODO 返回目标值 或 返回true 或 其他操作
    } else if (nums[mid] >= target) {
	    high = mid;
    } else {
    	low = mid + 1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

【题目】
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：
输入：nums = [], target = 0
输出：[-1,-1]

提示：
0 <= nums.length <= $10^5$
$-10^9$ <= nums[i] <= $10^9$
nums 是一个非递减数组
$-10^9$ <= target <= $10^9$

【核心思路】
区间可采用4种的任意一种，这里用闭区间：
由于目的是找到lower bound，因此当nums[mid]==target时，不直接返回low，而是继续更新high，直至找到target第一次出现的位置。故在while循环外再执行return。

测试用例1：

测试用例2：

测试用例1（开区间理解）：

【复杂度】
时间复杂度：$O(logn)$。
空间复杂度：$O(1)$。

【代码】

class Solution {
    public int lower_bound(int[] nums, int target) {
        //获取数组长度
        int n = nums.length;
        //定义区间左右端点
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            //定义中位数
            int mid = (low + high) / 2;
            //判断
            if (nums[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public int[] searchRange(int[] nums, int target) {
        //获取数组长度
        int n = nums.length;
        //定义结果数组
        int[] res = new int[2];
        //获取区间的左端点
        int start = lower_bound(nums, target);
        //特殊情况判断（不存在元素 / 不和目标值相等）
        if (start == n || nums[start] != target) {
            res[0] = -1;
            res[1] = -1;
            return res;
        }
        //获取区间的右端点（目标值下一个数的下界坐标的前一个位置）
        int end = lower_bound(nums, target + 1) - 1;
        //返回结果数组
        res[0] = start;
        res[1] = end;
        return res;
    }
}

2529. 正整数和负整数的最大计数

【说明】
#34 的配套习题
【题目】
给你一个按 非递减顺序 排列的数组 nums ，返回正整数数目和负整数数目中的最大值。
换句话讲，如果 nums 中正整数的数目是 pos ，而负整数的数目是 neg ，返回 pos 和 neg二者中的最大值。
注意：0 既不是正整数也不是负整数。

示例 1：
输入：nums = [-2,-1,-1,1,2,3]
输出：3
解释：共有 3 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 2：
输入：nums = [-3,-2,-1,0,0,1,2]
输出：3
解释：共有 2 个正整数和 3 个负整数。计数得到的最大值是 3 。

示例 3：
输入：nums = [5,20,66,1314]
输出：4
解释：共有 4 个正整数和 0 个负整数。计数得到的最大值是 4 。

提示：
1 <= nums.length <= 2000
-2000 <= nums[i] <= 2000
nums 按 非递减顺序 排列。

进阶：你可以设计并实现时间复杂度为 O(log(n)) 的算法解决此问题吗？

【核心思路】
负整数数量=数组中0首次出现的下标
正整数数量=数组长度-非正整数的个数=数组长度-数组中1首次出现的下标
下标采用标准二分查找（见#34的模板）

【复杂度】
时间复杂度：$O(logn)$。
空间复杂度：$O(1)$。

【代码】

class Solution {
    public int lower_bound(int[] nums, int target) {
        //获取数组长度
        int n = nums.length;
        //定义开区间左右端点
        int low = 0;
        int high = n - 1;
        //只要左端点不在右端点右侧，就继续循环
        while (low <= high) {
            //获取中位数
            int mid = low + (high - low) / 2;
            //判断
            if (nums[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public int maximumCount(int[] nums) {
        //获取数组长度
        int n = nums.length;
        //获取负整数的数量
        int neg = lower_bound(nums, 0);
        //获取正整数的数量（第一个≥1的位置=非正整数的个数，n-非正整数的个数=正整数个数）
        int pos = n - lower_bound(nums, 1);
        return Math.max(neg, pos);
    }
}

2300. 咒语和药水的成功对数

【说明】
#34 的配套习题
【题目】
给你两个正整数数组 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] 。

提示：
n == spells.length
m == potions.length
1 <= n, m <= $10^5$
1 <= spells[i], potions[i] <= $10^5$
1 <= success <= $10^{1}0$

【核心思路】
step1·首先，对药水数组potions升序排序，以实现二分查找
step2·遍历每个咒语spell，分别执行：
①计算目标target，将乘法转为除法

②若target未大于最后一个元素，表明存在成功的组合 => 计算满足条件的个数（在spells数组直接更新，降低空间复杂度）
③若target大于最后一个元素，表明不存在成功的组合 => 直接更新为0（在spells数组直接更新，降低空间复杂度）

以测试用例2为例：

【复杂度】
时间复杂度：$O((n+m)logm)$。数组排序$O(mlogm)$。总共n次二分查找，每个二分查找$O(logm)$，故for循环部分为$O(nlogm)$。总的为$O((n+m)logm)$。
空间复杂度：$O(1)$。忽略排序的栈开销，仅用到若干额外变量。

【代码】

class Solution {
    public int lower_bound(int[] nums, int target) {
        //获取数组长度
        int n = nums.length;
        //定义开区间左右端点
        int low = 0;
        int high = n - 1;
        //只要左端点不在右端点右侧，就继续循环
        while (low <= high) {
            //获取中位数
            int mid = low + (high - low) / 2;
            //判断
            if (nums[mid] >= target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        //获取两个数组的长度
        int n = spells.length;
        int m = potions.length;
        //数组排序
        Arrays.sort(potions);
        //遍历每个咒语
        for (int i = 0; i < n; i++) {
            //计算二分查找实际需要判断的target
            long target = (success - 1) / spells[i] + 1;
            //判断
            if (target <= potions[m - 1]) {
                spells[i] = m - lower_bound(potions, (int) target);
            } else {
                spells[i] = 0;
            }
        }
        return spells;
    }
}

参考：
1、灵神视频讲解
2、灵神视频讲解
3、灵神视频讲解
4、灵神解析