在有序数组中搜索给定的某个⽬标值的索引。再推⼴⼀点，如果⽬标值存在重复，修改版的⼆分查找可以返回⽬标值的左侧边界索引或者右侧边界索引。
寻找一个数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; // 注意
while(left <= right) {
int mid = (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;
}
- 为什么 while 循环的条件中是 <=，⽽不是 < ？
答：因为初始化 right 的赋值是 nums.length - 1，即最后⼀个元素的索引，⽽ 不是 nums.length。
寻找左侧边界的⼆分搜索
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int left_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = (left + right) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
寻找右侧边界的⼆分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int right_bound(int[] nums, int target) {
if (nums.length == 0) return -1;
int left = 0;
right = nums.length;
while (left < right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
if (left == 0) return -1;
return nums[left-1] == target ? (left-1) : -1;
}
应用示例
⾸先，算法要求的是「 H ⼩时内吃完⾹蕉的最⼩速度」，我们不妨称为 speed ，请问 speed 最⼤可能为多少，最少可能为多少呢？
显然最少为 1，最⼤为 max(piles) ，因为⼀⼩时最多只能吃⼀堆⾹蕉。那么暴⼒解法就很简单了，只要从 1 开始穷举到 max(piles) ，⼀旦发现发现某个值可以在 H ⼩时内吃完所有⾹蕉，这个值就是最⼩速度：
1
2
3
4
5
6
7
8
9
10
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 时间复杂度 O(N)
boolean canFinish(int[] piles, int speed, int H) {
int time = 0;
for (int n : piles) {
time += timeOf(n, speed);
}
return time <= H;
}
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;
}
注意这个 for 循环，就是在连续的空间线性搜索，这就是⼆分查找可以发挥作⽤的标志。由于我们要求的是最⼩速度，所以可以⽤⼀个搜索左侧边界的⼆分查找来代替线性搜索，提升效率：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int minEatingSpeed(int[] piles, int H) {
// 套⽤搜索左侧边界的算法框架
int left = 1, 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;
}
