二分查找算法及相关题目
二分查找（折半查找）算法是一种比较简单的算法，依赖于数组的有序，因为效率高，实现简单而且使用场景多而广泛存在。
1. 寻找右区间
来自力扣题库【436】题：寻找右区间
1.1 题目描述
给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个
都 不同 。
区间 i 的 右侧区间 可以记作区间 j ，并满足
，且
最小化 。
返回一个由每个区间 i 的右侧区间的最小起始位置组成的数组。如果某个区间 i 不存在对应的右侧区间 ，则下标 i 处的值设为 -1 。
注意：
-
-
-
-
每个间隔的起点都 不相同
1.2 示例数据
输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。
输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1, 0, 1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。
输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1, 2, -1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
1.3 解题思路
使用二分查找算法，对每一个 start 的起始位置的下标进行记录，然后再对 start 进行递增排序，之所以递增排序，是为了方便在后面的查找过程中对每一个区间的 end 进行二分查找。
具体看注释吧。
class Solution {
public int[] findRightInterval(int[][] intervals) {
Map<Integer, Integer> mapper = new TreeMap<>();
int n = intervals.length;
// 对特殊情况进行处理
if (n <= 1) return new int[]{-1};
// 然后把每一个 start 的位置 i 进行记录，并按照 start 进行递增排序
for (int i = 0; i < n; ++i) mapper.put(intervals[i][0], i);
// arr 用来保存mapper里面的 [start, idx] 数据对，之所以这么做，是为了方便二分查找
int[][] arr = new int[mapper.size()][2];
int idx = 0;
for (Map.Entry<Integer, Integer> entry : mapper.entrySet()) {
arr[idx][0] = entry.getKey();
arr[idx++][1] = entry.getValue();
}
// 构建返回值
int[] ret = new int[n];
for (int i = 0; i < n; ++i) {
// 对每一个 intervals[i][1]（end） 位置，都去找下一个大于等于 end 的下标
ret[i] = binarySearch(arr, intervals[i][1]);
}
return ret;
}
// 大于 target 的第一个位置
private int binarySearch(int[][] nums, int target) {
int left = 0, right = nums.length - 1;
// 看看是不是所有的起始位置，都没有这个 target 终止位置大，是的话说明这个target就不存在下一个起始点
if (nums[right][0] < target) return -1;
// 二分查找
while (left < right) {
int mid = left + (right - left) / 2;
// 如果找到了，就直接返回
if (nums[mid][0] == target) return nums[mid][1];
else if (nums[mid][0] < target) left = mid + 1;
else right = mid;
}
// 最后 left 位置就是大于 target 的第一个位置
return nums[left][1];
}
}
2. 找出第K小的距离对
来自力扣题库【719】题：找出第K小的距离对
2.1 题目描述
给定一个整数数组，返回所有数对之间的第 k 个最小距离。一对 (A, B) 的距离被定义为 A 和 B 之间的绝对差值。
注意：
-
2 <= len(nums) <= 10000. -
0 <= nums[i] < 1000000. -
1 <= k <= len(nums) * (len(nums) - 1) / 2.
2.2 示例数据
输入：
nums = [1,3,1]
k = 1
输出：0
解释：
所有数对如下：
(1,3) -> 2
(1,1) -> 0
(3,1) -> 2
因此第 1 个最小距离的数对是 (1,1)，它们之间的距离为 0。
2.3 解题思路
这是一道困难题，不过使用二分查找的话思路还是挺简单的。
首先转换一下思路，对于所有数对的第 k 个最小距离 x，那么 x 实际上是一个阈值，对于这个阈值，需要有 k 个小于等于它。而所有数对的差值，是可以枚举出来的（实际上不需要全部枚举，因为使用二分查找方法每次都淘汰掉这次的遍历数组个数的一半）。
还依赖于一个现成的思路：对于按非递减排序好的数组 nums，那么对于差值不大于 mid 的 nums[i, j] 区间，就已经有 j - i 个了（一个数组的最大值和最小值的差都小于等于 mid，那么最大值和最小值之间的任意两个数字之间的差值都不会大于 mid。
那么有了上面的初步思路以后，就可以首先对数组进行排序，然后就使用二分查找来完成最小距离的查找。
class Solution {
public int smallestDistancePair(int[] nums, int k) {
// 首先把数组进行排序，方便进行二分查找
Arrays.sort(nums);
// 这里的 low，指的是数组中两个数相差的最小值，high 是数组中两个值可能相差的最大值
int low = 0, high = nums[nums.length - 1] - nums[0];
while (low < high) {
// 找到差值的中间值，并尝试以 mid 来看是不是差值小于等于 mid 的数对个数符合要求 k
int mid = low + (high - low) / 2;
// count 用来统计所有的符合要求的情况，left 指针用来标记循环遍历整个数组的左边界
int count = 0, left = 0;
for (int right = 0; right < nums.length; ++right) {
// 在循环过程中，如果 nums[right] - nums[left] 大于了 mid，说明 left 太小了，这时候增大 left就可以使得数量减少
while (nums[right] - nums[left] > mid) ++left;
// 左右指针之间的数对都符合 nums[right] - nums[left] <= mid的要求
count += right - left;
}
// 如果符合差值小于等于 mid 的数对个数太多了（count >= k） 那么就减小最高值
if (count >= k) high = mid;
// 否则说明数对个数太少了，需要加大阈值 mid
else low = mid + 1;
}
// 到最后 low 就是最小的差值
return low;
}
}
3. 搜索旋转排序数组Ⅱ
来自力扣题库【81】：搜索旋转排序数组Ⅱ
3.1 题目描述
已知存在一个按非降序排列的整数数组 nums ，数组中的值不必互不相同。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转 ，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如，[0,1,2,4,4,4,5,6,6,7] 在下标 5 处经旋转后可能变为 [4,5,6,6,7,0,1,2,4,4] 。
给你 旋转后 的数组 nums 和一个整数 target ，请你编写一个函数来判断给定的目标值是否存在于数组中。如果 nums中存在这个目标值 target ，则返回 true ，否则返回 false 。
注意：
-
1 <= nums.length <= 5000 -
-104 <= nums[i] <= 104 -
题目数据保证 nums在预先未知的某个下标上进行了旋转 -
-104 <= target <= 104
3.2 示例数据
输入：nums = [2,5,6,0,0,1,2], target = 0
输出：true
输入：nums = [2,5,6,0,0,1,2], target = 3
输出：false
3.3 解题思路
两边各有序，本质上还是整体有序，所以使用二分搜索是比较棒的选择了，只不过需要在原来的二分搜索模板上加点东西。
这里有一个不同于上面题目的地方在于使用了递归方法来完成二分查找。
不过有一个潜在问题：如果数据正好反过来成了逆序呢，会不会递归栈溢出😵。
class Solution {
public boolean search(int[] nums, int target) {
return binarySearch(nums, target, 0, nums.length - 1);
}
private boolean binarySearch(int[] nums, int target, int left, int right) {
// 如果二分搜索左右边界都遇到了，意味着搜索到了最后一个元素，看看这个数和 target 是否相同
if (left >= right) return nums[left] == target;
// 否则的话，找到二分中点位置
int mid = left + (right - left) / 2;
// 看看二分中点位置数是不是 target
if (nums[mid] == target) return true;
else if (nums[mid] < target) {
// 如果偏小了，那么有两种情况需要递归
// 首先是如果 [left, right] 不是整体有序的话（nums[left] >= nums[right]），就需要再对整体分别递归
if (nums[left] >= nums[right]) return binarySearch(nums, target, left, mid) || binarySearch(nums, target, mid + 1, right);
// 如果 [left, right] 已经整体有序了（走到了非递减子序列中），那么使用普通的二分查找就好了
else return binarySearch(nums, target, mid + 1, right);
} else {
// 同上面思路一样~
if (nums[left] >= nums[right]) return binarySearch(nums, target, left, mid) || binarySearch(nums, target, mid + 1, right);
else return binarySearch(nums, target, left, mid);
}
}
}
4. 寻找旋转排序数组中的最小值
来自力扣题库【153】：寻找旋转排序数组中的最小值
4.1 题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7]在变化后可能得到：若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
注意：
-
n == nums.length -
1 <= n <= 5000 -
-5000 <= nums[i] <= 5000 -
nums中的所有整数 互不相同` -
nums原来是一个升序排序的数组，并进行了1至n次旋转
4.2 示例数据
输入：nums = [3,4,5,1,2]
输出：1
解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
输入：nums = [4,5,6,7,0,1,2]
输出：0
解释：原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
输入：nums = [11,13,15,17]
输出：11
解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
4.3 解题思路
嗯？又是旋转数组！不过这次不是找指定值 target ，但是难度没变都是中等的。
二分查找，因为对于最小值 min 来说，它的左边一定都是大于它的，所以当整个序列的中间值都大于最右边元素的话，说明左边整个子序列都是比 min 大的，最小值一定在右边子序列中，那么只需要右移 left 指针就好了。否则的话，说明整个序列的中间元素要小于最右边的元素，这时候最小值一定在左边，就需要左移 right 指针。
class Solution {
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = (right - left) / 2 + left;
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
return nums[left];
}
}
5. 寻找旋转排序数组中的最小值 II
来自力扣题库【154】：寻找旋转排序数组中的最小值Ⅱ
5.1 题目描述
已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,4,4,5,6,7] 在变化后可能得到：
-
若旋转 4次，则可以得到[4,5,6,7,0,1,4] -
若旋转 7次，则可以得到[0,1,4,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个可能存在 重复 元素值的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
注意：
-
n == nums.length -
1 <= n <= 5000 -
-5000 <= nums[i] <= 5000 -
nums原来是一个升序排序的数组，并进行了1至n次旋转
5.2 示例数据
输入：nums = [1,3,5]
输出：1
输入：nums = [2,2,2,0,1]
输出：0
5.3 解题思路
呵！这次直接好家伙😮，竟然又是旋转数组！不过这次的是困难题，允许了数组里有重复值😱，这么一来就会造成一些不同，但总体还是使用二分查找来找最小值。
使用二分查找方法，对数组进行查找就好了，不过需要修改边界缩进策略：
-
如果 nums[mid] < nums[right]那么说明nums[mid, right]中间的元素一定不是最小值，所以只需要让right = mid就好了。 -
如果 nums[mid] > nums[right]那么说明nums[left, mid]中间的元素一定不是最小值（包括mid位置），直接让left = mid + 1就好了。 -
如果 nums[mid] == nums[right]那么需要略微调整right指针，因为数组中存在重复数据，比如[2, 2, 2, 1, 2]的情况，那么就需要一点一点缩小right来筛选出最小值。
class Solution {
public int findMin(int[] nums) {
// 左右边界指针
int left = 0, right = nums.length - 1;
while (left < right) {
// 找到中间位置
int mid = left + (right - left) / 2;
// 如果中间位置元素小于右边界元素，说明中间位置元素有可能是最小值
if (nums[mid] < nums[right]) right = mid;
// 如果中间元素大于了右边界元素，那么说明从 left 到 mid 的元素都不可能是最小值，直接调整左边界
else if (nums[mid] > nums[right]) left = mid + 1;
// 如果相同的话，只能一步一步缩小右边界来找最小值了，因为可能有重复值
else right--;
}
return nums[left];
}
}
6. 分割数组的最大值
来自力扣题库【410】：分割数组的最大值
6.1 题目描述
给定一个非负整数数组 nums 和一个整数 m ，你需要将这个数组分成 m 个非空的连续子数组。
设计一个算法使得这 m 个子数组各自和的最大值最小。
注意：
-
1 <= nums.length <= 1000 -
0 <= nums[i] <= 106 -
1 <= m <= min(50, nums.length)
6.2 示例数据
输入：nums = [1,2,3,4,5], m = 2
输出：9
输入：nums = [1,4,4], m = 3
输出：4
6.3 解题思路
使用二分查找的方法来对最小和进行查找。首先找到整个序列的最大值来当作二分查找的左边界 left ，并求得整个序列的累加和作为右边界 right。因为这两个值代表着最终答案的可行区间，也就是把数组不管怎样切分，每个子数组的和最大值都不会小于 left，也不会大于 right，那么再对这个区间进行二分查找就好了。
然后通过判断切分个数 count 和 m 的关系来判断是否是一个可行的答案。
class Solution {
public int splitArray(int[] nums, int m) {
// left 记录整个序列中最大值，right 记录整个序列的和
int left = 0, right = 0;
for (int num : nums) {
right += num;
if (left < num) left = num;
}
// 在下面的二分查找过程中，left 和 right 是不断缩小的（废话）
// [left, right] 总是包含着可分成 m 个子数组的最小和 mid
while (left < right) {
// mid 用来找最符合条件的区间和
int mid = (right - left) / 2 + left;
if (check(nums, mid, m)) {
// 如果 mid 太大了（right太大），
// 那么整个区间划分得到的子数组个数就小于等于 m，
// check 返回 true，这时候就需要减小 right
right = mid;
} else {
// 如果 mid 太小了（left太小），
// 那么整个区间划分得到的子数组个数就很多 check 就返回 false，
// 这时候就需要加大 left
left = mid + 1;
}
}
return left;
}
// 检查区间按照 最大和为 x 划分时，能否分成 多少 个。
private boolean check(int[] nums, int x, int m) {
// count 是数组个数，sum 是当前数组累加和
int count = 1, sum = 0;
for (int num : nums) {
if (sum + num > x) {
// 如果加上当前数 num 就大于了限制条件 x，那么就重新开始一个子数组，而且分组个数 count + 1
sum = num;
count++;
} else {
// 否则的话，就直接往当前子数组中累加和
sum += num;
}
}
return count <= m;
}
}
总的来说这次的专题训练还是很顺利的，没有太难没有太偏，可能是因为这块真的不太难😯
恭喜呀，成功晋级🌹
2021年4月12日