二分搜索
- 二分搜索模板
- 二分搜索运用
图片来源于网络
1. 二分搜索模板
二分搜索（二分查找）也称折半查找（Binary Search），是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
二分搜索框架如下：
int binarySearch(int[] nums, int target) {
int left = 0, right = ...;
while(...) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
...
} else if (nums[mid] < target) {
left = ...
} else if (nums[mid] > target) {
right = ...
}
}
return ...;
}
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。
1.1 基本的二分搜索
/**
* 寻找一个数（基本的二分搜索）
* <p>
* 搜索一个数，如果存在，返回其索引，否则返回 -1
* <p>
* 缺陷：针对如 nums = [1,2,2,2,3]，target为 2 时，此算法返回的索引是 2，而无法处理左侧边界索引1和右侧边界索引3
* <p>
* 初始化 right = nums.length - 1，决定了「搜索区间」是 [left, right]
* 决定了 while (left <= right)，同时也决定了 left = mid+1 和 right = mid-1
* <p>
* 只需找到一个 target 的索引即可，当 nums[mid] == target 时可以立即返回
*/
private int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
// [left, right]，终止条件是 left == right + 1
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 直接返回
return mid;
} else if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// right = ...
right = mid - 1;
}
}
return -1;
}
1.2 寻找左侧边界的二分搜索
/**
* 寻找左侧边界的二分搜索
* <p>
* 初始化 right = nums.length，决定了「搜索区间」是 [left, right)
* 决定了 while (left < right)，同时也决定了 left = mid + 1 和 right = mid
* <p>
* 因为需找到 target 的最左侧索引，所以当 nums[mid] == target 时不要立即返回
* 而要收紧右侧边界以锁定左侧边界
*/
private int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
// [left, right)，终止的条件是 left == right
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
// left = ...
left = mid + 1;
} else if (nums[mid] > target) {
// right = ...
right = mid;
}
}
return left;
}
当然，上面算法也可以使用两边都闭的「搜索区间」来实现：
/**
* 寻找左侧边界的二分搜索 [left, right]
*/
private int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 别返回，锁定左侧边界 (收缩右侧边界)
right = mid - 1;
} else if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target) return -1;
return left;
}
1.3 寻找右侧边界的二分搜索
/**
* 寻找右侧边界的二分搜索
* <p>
* 初始化 right = nums.length，决定了「搜索区间」是 [left, right)
* 决定了 while (left < right)，同时也决定了 left = mid + 1 和 right = mid
* <p>
* 需找到 target 的最右侧索引，当 nums[mid] == target 时不要立即返回
* 而要收紧左侧边界以锁定右侧边界
* <p>
* 又因为收紧左侧边界时必须 left = mid + 1，所以最后无论返回 left 还是 right，必须减一
*/
private int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length;
// [left, right)
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
// 收紧左侧边界以锁定右侧边界
left = mid + 1;
} else if (nums[mid] < target) {
// left = ...
left = mid + 1;
} else if (nums[mid] > target) {
// right = ...
right = mid;
}
}
// return left - 1; // or return right - 1;
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
}
同样的，上面算法也可以使用两边都闭的「搜索区间」来实现：
/**
* 寻找右侧边界的二分搜索 [left, right]
*/
private int right_bound(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
// 别返回，锁定右侧边界 (收缩左侧边界)
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target) return -1;
return right;
}
小结：
- 分析二分查找代码时，不要出现
else，全部展开成else if方便理解。 - 注意「搜索区间」和
while的终止条件，如果存在漏掉的元素，记得在最后检查。 - 如需定义左闭右开的「搜索区间」搜索左右边界，只要在
nums[mid] == target时做修改即可，搜索右侧时需要减一。 - 如果将「搜索区间」全都统一成两端都闭，只要稍改
nums[mid] == target条件处的代码和返回的逻辑即可。
2. 二分搜索的运用
二分搜索除了在有序数组中搜索给定的某个目标值的索引，当搜索空间有序的时候，也可以过二分搜索「剪枝」，大幅提升效率。
2.1 爱吃香蕉的珂珂
力扣 875 题如下：
爱吃香蕉的珂珂
上面题目用暴力解法比较容易写出如下代码：
/**
* 暴力解法
* <p>
* Koko 每小时最多吃一堆香蕉，如果吃不下的话留到下一小时再吃；
* 如果吃完了这一堆还有胃口，也只会等到下一小时才会吃下一堆。
* 在这个条件下，确定珂珂吃香蕉的最小速度（根/小时）
* <p>
* 算法要求的「H小时内吃完香蕉的最小速度」speed，显然最少为 1，最大为 max(piles)
*/
private int minEatingSpeed(int[] piles, int H) {
// piles 数组的最大值
int max = getMax(piles);
for (int speed = 1; speed < max; speed++) {
// 以 speed 是否能在 H 小时内吃完香蕉
if (canFinish(piles, speed, H)) {
return speed;
}
}
return max;
}
值得注意的是，上面的 for 循环是在连续的空间线性搜索，也就是二分查找可以发挥作用的标志。
用寻找左侧边界的二分搜索来代替线性搜索，如下：
/**
* 借助二分查找技巧，算法的时间复杂度为 O(NlogN)
*/
int minEatingSpeed(int[] piles, int H) {
int left = 1;
int right = getMax(piles) + 1;
// 套用 寻找左侧边界的二分搜索 框架
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(piles, mid, H)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/**
* 在规定时间内是否能吃完香蕉
*
* @param piles 香蕉数量
* @param speed 吃香蕉速度
* @param H 规定时间
*/
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
/**
* 吃一堆香蕉的时间
*
* @param n 一堆香蕉的个数
* @param speed 吃香蕉的速度
*/
int timeOf(int n, int speed) {
return (n / speed) + ((n % speed > 0) ? 1 : 0);
}
/**
* 数组最大值
*/
int getMax(int[] piles) {
int max = 0;
for (int n : piles) {
max = Math.max(n, max);
}
return max;
}
2.2 包裹运输问题
力扣 1011 题如下：
在 D 天内送达包裹的能力
上面题目本质上和珂珂吃香蕉的问题是一样的，需要确定运输的最小载重，假设其最小值和最大值分别为 max(weights) 和 sum(weights)，用寻找左侧边界的二分搜索优化线性搜索如下：
/**
* 最小载重
*/
int shipWithDays(int[] weights, int D) {
// 载重可能的最小值
int left = getMax(weights);
// 载重可能的最大值 + 1
int right = getSum(weights) + 1;
// 套用 寻找左侧边界的二分搜索 框架
while (left < right) {
int mid = left + (right - left) / 2;
if (canFinish(weights, mid, D)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
/**
* 若载重为 cap，是否能在 D 天内运完货物？
*/
boolean canFinish(int[] weights, int cap, int D) {
int i = 0;
for (int day = 0; day < D; day++) {
int maxCap = cap;
while ((maxCap -= weights[i]) >= 0) {
i++;
if (i == weights.length) {
return true;
}
}
}
return false;
}
/**
* 数组最大值
*/
int getMax(int[] piles) {
int max = 0;
for (int n : piles) {
max = Math.max(n, max);
}
return max;
}
/**
* 数组和
*/
int getSum(int[] weights) {
int sum = 0;
for (int n : weights) {
sum += n;
}
return sum;
}
2.3 分割数组的最大值
力扣 410 题如下：
分割数组的最大值
上面题目是固定了 m 的值，让我们确定一个最大子数组和；那可以反过来，限制一个最大子数组的和 max，来反推最大子数组的和为 max 时，至少可以将 nums 分割成几个子数组。定义函数如下：
/**
* 在每个子数组和不超过 max 的条件下，计算 nums 至少可以分割成几个子数组
*
* 如 nums = [7,2,5,10]，若 max = 10，则split函数返回 3，
* 即 nums 数组最少能分割成三个子数组，分别是[7,2],[5],[10]
*/
int split(int[] nums, int max);
若能找到一个最小的 max 值，满足上述函数 split(nums, max) 的结果和 m 相等，那么这个 max 值不就是符合题意的「最小的最大子数组的和」吗？
接下来对 max 进行穷举，子数组至少包含一个元素，至多包含整个数组，那么最大子数组的和 max 的取值范围是闭区间 [max(nums), sum(nums)]，即最大元素值到整个数组和之间，如下所示：
/**
* 计算最大子数组的和
*/
int splitArray(int[] nums, int m){
int low = getMax(nums);
int high = getSum(nums);
for (int max = low; max <= high; max++){
// 如果最大子数组和是 max，至少可以把 nums 分割成 n 个子数组
int n = split(nums, max);
// 为什么是 <= 不是 == ？
// split 函数采用了贪心的策略，计算的是 max 限制下至少能够将 nums 分割成几个子数组
if (n <= m){
return max;
}
}
return -1;
}
/**
* 在每个子数组和不超过 max 的条件下，计算 nums 至少可以分割成几个子数组
*
* 如 nums = [7,2,5,10]，若 max = 10，则split函数返回 3，
* 即 nums 数组最少能分割成三个子数组，分别是[7,2],[5],[10]
*/
int split(int[] nums, int max){
// 至少可以分割的子数组数量
int count = 1;
// 记录每个子数组的元素和
int sum = 0;
for (int i = 0; i< nums.length; i++){
if (sum + nums[i] > max){
// 如果当前子数组和大于 max 限制，则这个子数组不能再添加元素了
count++;
sum = nums[i];
} else {
// 当前子数组和还没达到 max 限制，还可以添加元素
sum += nums[i];
}
}
return count;
}
/**
* 数组最大值
*/
int getMax(int[] nums) {
int max = 0;
for (int n : nums) {
max = Math.max(n, max);
}
return max;
}
/**
* 数组和
*/
int getSum(int[] nums) {
int sum = 0;
for (int n : nums) {
sum += n;
}
return sum;
}
上面代码是用暴力解法实现的，由于 split 是单调函数，且符合二分查找技巧进行优化的标志，因此可用二分搜索进行优化。
因为算法返回最小的那个 max，所以用寻找左侧边界的二分搜索优化如下：
/**
* 计算最大子数组的和
* <p>
* 假设 nums 元素个数为 N，元素和为 S，则 split 函数的复杂度为 O(N)，二分查找的复杂度为 O(logS)，
* 所以算法的总时间复杂度为 O(N*logS)
*/
int splitArray(int[] nums, int m) {
int left = getMax(nums);
// 一般搜索区间是左开右闭的，所以 right 要额外加一
int right = getSum(nums) + 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 根据分割子数组的个数收缩搜索区间
int n = split(nums, mid);
if (n == m) {
// 收缩右边界，达到搜索左边界的目的
right = mid;
} else if (n < m) {
// 最大子数组和上限高了，减小一些
right = mid;
} else if (n > m) {
// 最大子数组和上限低了，增加一些
left = mid + 1;
}
}
return left;
}
int split(int[] nums, int max) {... }
int getMax(int[] nums) {... }
int getSum(int[] nums) {... }
小结：
二分查找在实际问题中的应用，首先思考使用 for 循环暴力解决问题，观察代码是否如下形式：
for (int i = 0; i < n; i++){
if (isOK(i)) return answer;
}
如果是，那么就可以使用二分搜索优化搜索空间：如果要求最小值就是搜索左侧边界的二分，如果要求最大值就用搜索右侧边界的二分。
参考链接：
