二分查找
Ⅰ 解题框架
分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚，这样可以清楚地展现所有细节。其中 ... 标记的部分，就是可能出现细节问题的地方，当你见到一个二分查找的代码时，首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。
另外声明一下，计算 mid 时需要防止溢出，代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。
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 ...;
}
①寻找一个数（基本的二分搜索即搜索一个数，如果存在，返回其索引，否则返回 -1。
因为我们初始化 right = nums.length - 1
所以决定了我们的「搜索区间」是 [left, right]
所以决定了 while (left <= right)
同时也决定了 left = mid+1 和 right = mid-1
因为我们只需找到一个 target 的索引即可
所以当 nums[mid] == target 时可以立即返回
int binarySearch(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)
return mid;
else if (nums[mid] < target)
left = mid + 1; // 注意
else if (nums[mid] > target)
right = mid - 1; // 注意
}
return -1;
}
- 初始化
right的赋值是nums.length - 1，即最后一个元素的索引，而不是nums.length。因此用while(left<=right)，搜索区间为[left,right]。 - 那 while 循环什么时候应该终止？搜索区间为空的时候应该终止，意味着你没得找了，就等于没找到嘛。
while(left <= right)的终止条件是left == right + 1，写成区间的形式就是[right + 1, right]，或者带个具体的数字进去[3, 2]，可见这时候区间为空。
②寻找左侧边界的二分搜索
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最左侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧右侧边界以锁定左侧边界
int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
// 搜索区间为 [left, right]
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
// 搜索区间变为 [mid+1, right]
left = mid + 1;
} else if (nums[mid] > target) {
// 搜索区间变为 [left, mid-1]
right = mid - 1;
} else if (nums[mid] == target) {
// 收缩右侧边界
right = mid - 1;
}
}
// 检查出界情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
由于 while 的退出条件是 left == right + 1，所以当 target 比 nums 中所有元素都大时，会存在以下情况使得索引越界：
image-20201213111413470
③寻找右侧边界
因为我们初始化 right = nums.length
所以决定了我们的「搜索区间」是 [left, right)
所以决定了 while (left < right)
同时也决定了 left = mid + 1 和 right = mid
因为我们需找到 target 的最右侧索引
所以当 nums[mid] == target 时不要立即返回
而要收紧左侧边界以锁定右侧边界
又因为收紧左侧边界时必须 left = mid + 1
所以最后无论返回 left 还是 right，必须减一
int right_bound(int[] nums, int target) {
int left = 0, 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) {
right = mid - 1;
} else if (nums[mid] == target) {
// 这里改成收缩左侧边界即可
left = mid + 1;
}
}
// 这里改为检查 right 越界的情况，见下图
if (right < 0 || nums[right] != target)
return -1;
return right;
}
axaiuc
Ⅱ 相关习题
1、在排序数组中查找元素的左右边界（LeetCode 34）
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
int l = leftBundSearch(nums,target);
int r = l;
if (l != -1) { //寻找右边界
for (int i=l+1;i<nums.length;i++) {
if (nums[i] == nums[l]) {
r = i;
} else {
break;
}
}
}
res[0] = l;
res[1] = r;
return res;
}
//寻找左边界
int leftBundSearch (int[] nums,int target) {
int len = nums.length;
if (len == 0 || target>nums[len-1] || target<nums[0]) {
return -1;
}
int left = 0;
int right = len-1;
while (left <= right) {
int mid = left+(right-left)/2;
if (nums[mid] > target) {
right = mid-1;
}else if (nums[mid] < target) {
left = mid+1;
}else if (nums[mid] == target) {
right = mid-1;
}
}
if (left >= len || nums[left] != target) return -1;
return left;
}
}
2、吃香蕉的最小速度（LeetCode 875）
image-20201213183741318
分析题目可知吃香蕉的最小速度为1，最大速度就是数组piles[]元素的最大值。可以把最小速度看成left，最大速度看成right，从而进行二分查找。
注意：因为此题目肯定是有解的（因为速度为数组最大值时肯定能吃完），因此二分查找结束后不需要检查left是否越界。
class Solution {
public int minEatingSpeed(int[] piles, int H) {
int right = getMax(piles); //最大速度
int left = 1; //最小速度
while (left <= right) {
int mid = left + (right-left)/2;
if (canFinish(piles,H,mid)) {
right = mid-1;
}else {
left = mid+1;
}
}
//因为必然有解，因此不需要进行越界检查
return left;
}
boolean canFinish (int[] piles,int H,int speed) {
int hours = 0;
for (int j=0;j<piles.length;j++) {
if (piles[j]%speed == 0) {
hours += piles[j]/speed;
} else {
hours += piles[j]/speed + 1;
}
}
return hours>H?false:true;
}
int getMax (int[] piles) {
int max = -1;
for (int item:piles) {
if (item > max) {
max = item;
}
}
return max;
}
}
3、在D天内送达包裹的能力（LeetCode 1011）
image-20201213190823112
类似于上一题：
class Solution {
public int shipWithinDays(int[] weights, int D) {
int left = getMax(weights); //最小运输能力
int right = getSum (weights);//最大运输能力
while (left <= right) {
int mid = left+(right-left)/2;
if (canFinish(weights,D,mid)) {
right = mid-1;
}else {
left = mid+1;
}
}
return left;
}
boolean canFinish (int[] weights,int D,int cap) {
int days = 0;
int index = 0;
int tmpCap = cap;
while (index < weights.length) {
while (index < weights.length && (tmpCap -= weights[index]) >= 0) {
index++;
}
days++;
tmpCap = cap;
}
return days>D?false:true;
}
int getMax (int[] weights) {
int max = -1;
for (int item:weights) {
if (item > max) {
max = item;
}
}
return max;
}
int getSum (int[] weights) {
int sum = 0;
for (int item:weights) {
sum += item;
}
return sum;
}
}
