剑指offer（专项突破版）11 二分查找
分析
若找到，返回位置，若没找到，返回left。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while(left <= right){
int mid = (left + right) / 2;
if(nums[mid] == target){
return mid;
}
else if(nums[mid] > target){
right = mid - 1;
}
else{
left = mid + 1;
}
}
return left;
}
};
|
分析
题目保证给定的数组是一个山脉数组。即对于mid，如果大于左边和右边的元素，则为峰顶；如果大于左边小于右边，则峰顶在右边区域；如果小于左边大于右边，则在左边区域。在比较时需要注意索引是否合法，当mid=0时，不用再比较左边，当mid=n-1时，不需要再比较右边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int left = 1;
int right = arr.size() - 2;
while(left <= right){
int mid = (left + right) / 2;
if(arr[mid] > arr[mid-1] && arr[mid] > arr[mid+1]){
return mid;
}
else if(arr[mid] > arr[mid-1] && arr[mid] < arr[mid+1]){
left = mid + 1;
}
else{
right = mid - 1;
}
}
return -1;
}
};
|
分析
数组中的数字每两个分成一组，最初的若干组的两个数字都是相同的。但遇到了只出现一次的数字之后，情况发生变化。这个只出现一次的数字和后面的数字结合成一组，导致后面所有出现两次的数字都被分到两个不同的组，即后面所有组的两个数字都不相同。由此可见，只出现一次的数字正好是第1个两个数字不相等的分组的第1个数字。
接着考虑如何用二分查找的思路来解决这个问题。将数组中的数字每两个分为一组。先找出位于中间的一组，确定这一组的两个数字是否相同。如果两个数字相同，那么那个只出现一次的数字一定在它的后面，因此接着查找它的后半部分。如果两个数字不相同，那么接着检查这一组是不是第1组两个数字不相同的分组。如果是第1组，那么这一组的第1个数字就是只出现一次的数字。如果不是第1组，那么第1组一定在它的前面，因此接着查找它的前半部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int left = 0;
int right = nums.size() / 2;
while(left <= right){
int mid = (left + right) / 2;
int i = mid * 2;
if(i < nums.size() - 1 && nums[i] != nums[i+1]){
if(mid == 0 || nums[i-2] == nums[i-1]){
return nums[i];
}
right = mid - 1;
}
else{
left = mid + 1;
}
}
return nums[nums.size() - 1];
}
};
|
分析
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| class Solution {
public:
vector<int> sums;
Solution(vector<int>& w) {
sums.resize(w.size(), 0);
int sum = 0;
for(int i = 0; i < w.size(); i++){
sum += w[i];
sums[i] = sum;
}
}
int pickIndex() {
int p = rand() % sums.back() + 1;
int left = 0;
int right = sums.size() - 1;
while(left <= right){
int mid = (left + right) / 2;
if(p <= sums[mid]){
if(mid == 0 || p > sums[mid-1]){
return mid;
}
right = mid - 1;
}
else{
left = mid + 1;
}
}
return -1;
}
};
|
分析
假设输入的非负整数为n。解决这个问题的直观方法是从0开始每次增加1，对于每个整数m，判断m2是否小于或等于n。如果找到一个m，并且满足m2≤n和（m+1）2>n，那么m就是n的平方根。这种直观的解法从0一直试到n的平方根，因此时间复杂度是O（n0.5）。
由数学常识可知，整数n的平方根一定小于或等于n。同时，除0之外的所有整数的平方根都大于或等于1。因此，整数n的平方根一定在从1到n的范围内，取这个范围内的中间数字m，并判断m2是否小于或等于n。如果m2≤n，那么接着判断（m+1）2是否大于n。如果满足（m+1）2>n，那么m就是n的平方根。如果m2≤n并且（m+1）2≤n，则n的平方根比m大，接下来搜索从m+1到n的范围。如果m2>n，则n的平方根小于m，接下来搜索从1到m-1的范围。然后在相应的范围内重复这个过程，总是取出位于范围中间的m，计算m2和（m+1）2并与n比较，直到找到一个满足m2≤n并且（m+1）2>n的m。
这种思路每次都取某个范围的中间值，如果中间值满足条件，则搜索结束；如果中间值不满足条件，则该中间值将下一轮搜索的范围缩小一半。这正是典型的二分查找的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int mySqrt(int x) {
int left = 1;
int right = x;
while(left <= right){
int mid = left + (right - left) / 2;
if(mid <= x / mid){
if((mid + 1) > x / (mid + 1)){
return mid;
}
left = mid + 1;
}
else{
right = mid - 1;
}
}
return 0;
}
};
|
- 时间复杂度：二分查找算法每次将搜索范围缩小一半，从1到n的范围只需要搜索O（logn）次，因此基于二分查找的解法的时间复杂度是O（logn）。
- 空间复杂度：O(1)
分析
狒狒吃香蕉的速度应该介于每小时吃1~最大堆香蕉数，因此可以用二分查找，如果以mid为速度吃完所有香蕉的时间大于警卫离开的时间，就在右边部分找，否则在左半部分找。结束的条件是当前mid的时间小于等于H且mid-1的时间大于H，或者mid=1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int getHours(vector<int>& piles, int k){
int res = 0;
for(auto& num : piles){
res += num / k;
res += num % k > 0 ? 1 : 0;
}
return res;
}
int minEatingSpeed(vector<int>& piles, int h) {
int left = 1;
int right = *max_element(piles.begin(), piles.end());
while(left <= right){
int mid = (left + right) / 2;
if(getHours(piles, mid) <= h){
if(mid == 1 || getHours(piles, mid-1) > h){
return mid;
}
right = mid - 1;
}
else{
left = mid + 1;
}
}
return -1;
}
};
|
- 时间复杂度：如果总共有m堆香蕉，最大一堆香蕉的数目为n，函数minEatingSpeed在1到n的范围内做二分查找，需要尝试O（logn）次，每尝试一次需要遍历整个数组求出按某一速度吃完所有香蕉需要的时间，因此总的时间复杂度是O（mlogn）。
- 空间复杂度：O(1)
总结
本章介绍了二分查找算法。如果要求在一个排序数组中查找一个数字，那么可以用二分查找算法优化查找的效率。二分查找算法的基本思路是在查找范围内选取位于中间的数字。如果中间数字刚好符合要求，那么就找到了目标数字。如果中间数字不符合要求，则比较中间数字和目标数字的大小并相应地确定下一轮查找的范围是当前查找范围的前半部分还是后半部分。由于每轮查找都将查找范围缩小一半，如果排序数组的长度为n，那么二分查找算法的时间复杂度是O（logn）。
二分查找除了可以在排序数组中查找某个数字，还可以在数值范围内实现快速查找。可以先根据数值的最小值和最大值确定查找范围，然后按照二分查找的思路尝试数值范围的中间值。如果这个中间值不符合要求，则尝试数值范围的前半部分或后半部分。