二分查找

二分查找/折半查找的基本方法

二分查找

题目

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

  1. 示例 1:

    输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4

  2. 示例 2:

    输入: nums = [-1,0,3,5,9,12], target = 2 输出: -1

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums[0]==target) return 0;
if(nums[nums.size()-1]==target) return (nums.size()-1);
int pre=0,pos=nums.size()-1,mid=(pre+pos)/2;
while(nums[mid]!=target){
if(nums[mid]<target) pre=mid+1;
else pos=mid-1;
mid=(pre+pos)/2;
if(pre>pos) return -1;
}
return mid;
}
};
judge

总结
  1. vector属于C++ STL的container,相当于栈这种数据结构,实用性很强,需要掌握!这里涉及到的有vector的随机访问 (下标从0开始)和vector.size() 的方法。
  2. 二分查找使用到了三个指针变量 。三个指针起名为lowmidhigh更为规范。

第一个错误的版本

题目

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的

假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数

  1. 示例 1:输入:n = 5, bad = 4 输出:4

  2. 示例 2:输入:n = 1, bad = 1 输出:1

提示:1 <= bad <= n <= 231 - 1

最初的想法: 在二分查找的基础上,修改查命中的条件为!(isBadVersion(mid)&&isBadVersion(mid-1)) (即终止条件为mid指向错误的版本且靠近mid左边的第一个版本是正确的版本)。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int firstBadVersion(int n) {
int low=1,high=n,mid=0;
while(!isBadVersion(mid)||isBadVersion(mid-1)){
mid=low+(high-low)/2;
if(isBadVersion(mid)) high=mid-1;
else low=mid+1;
}
return mid;
}
};
judge1

看起来结果还算不赖,但是每次循环都会调用3次API,显然,与题目要求尽可能减少API的调用不符!

改进的做法: 不断地缩小边界至三个指针重合,这时候要查找的一定就是三个指针重合时指向的值 。这样每次循环只调用一次API。
1
2
3
4
5
6
7
8
9
10
11
public:
int firstBadVersion(int n) {
int low = 1, high = n, mid = 0;
while (low<high){
mid = low + ((high - low)/2);
if(isBadVersion(mid)) high = mid;
else low = mid + 1;
}
return low;
}
};
judge2

这个做法确实比之前高明一些,但是也有例外。因为这个算法时间复杂度是妥妥的$O(logn)$,但之前的做法是最坏时间复杂度为$O(logn)$

总结
  1. 学习对(low+high)/2 可能溢出的处理:使用low+(high-low)/2
  2. 注意方法二缩小右边界时应该是high=mid 而不是high=mid-1 !因为如果此时mid刚好指向第一个错误的版本,那么high=mid-1之后,mid就永远不可能再指向这个值了,最终返回的就是一个错误的值!(这甚至让我一度怀疑算法的正确性……)

搜索插入位置

本题相当于是第一题二分算法的补充,额外研究了当查找失败时target应该插入的位置。

题目

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请务必使用时间复杂度为 O(log n) 的算法。

  1. 示例 1:输入: nums = [1,3,5,6], target = 5 输出: 2
  2. 示例 2:输入: nums = [1,3,5,6], target = 2 输出: 1
  3. 示例 3:输入: nums = [1,3,5,6], target = 7 输出: 4
  4. 示例 4:输入: nums = [1,3,5,6], target = 0 输出: 0
  5. 示例 5:输入: nums = [1], target = 0 输出: 0
  1. 1 <= nums.length <= $10^4$​

  2. $-10^4$<= nums[i] <= $10^4$

  3. nums 为无重复元素的升序排列数组
  4. $-10^4$​ <= target <= $10^4$​​

……总之就是不用考虑溢出。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int low=0,high=nums.size()-1,mid=0;
while(nums[mid]!=target){
mid=(low+high)/2;
if(nums[mid]<target) low=mid+1;
else high=mid-1;
if(low>high) return low;
}
return mid;
}
};
jugde

总结

·思考为什么查失败时应该返回low而不是high或mid。

证明:由low和high指针的对称性,可知查失败的情况下当low=mid=high时,nums[mid]可能小于target,也可能大于targe

  1. 若nums[mid]<target,那么low=mid+1;而target应该插入到nums[mid]之后的一位,即low。

  2. 若nums[mid]>target,那么high=mid-1;而target应该插入到nums[mid]所在的位置,即low。

所以,导致插入位置不对称的原因是插入的值要和前后的值满足一定的大小关系……这么说可能会有点抽象……总而言之就和上面是一个意思。


双指针

怎么说呢,这种题就像脑筋急转弯,想到了正确的做法就能做对,没有固定的解法。但是,掌握更多的技巧,有助于拓宽解题思路,在更短的时间内想出更为高效的算法。

有序数组的平方

题目

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

  1. 示例 1:输入:nums = [-4,-1,0,3,10] 输出:[0,1,9,16,100]
  2. 示例 2:输入:nums = [-7,-3,2,3,11] 输出:[4,9,9,49,121]
思路一: 从正负分界处切断,两段的平方都是有序的。再利用归并排序 的思想对两段进行合并。
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:
vector<int> sortedSquares(vector<int>& nums) {
vector<int> vi;
int j=0,len=nums.size();
while(j<len && nums[j]<0) j++;
int i=j-1;
while(i>=0 || j<len){
if(i<0){
vi.push_back(nums[j]*nums[j]);
j++;
}
else if(j>=len){
vi.push_back(nums[i]*nums[i]);
i--;
}
else if((nums[i]+nums[j])<0){
vi.push_back(nums[j]*nums[j]);
j++;
}
else{
vi.push_back(nums[i]*nums[i]);
i--;
}
}
return vi;
}
};
judge1

思路二: 从两端开始,往中间收拢,性能极高。这个方法我一开始没有想到,看到题解之后就去试了试这个思路,然后看了看跑分,直呼卧槽!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int i=0,j=nums.size()-1,flag=j;
vector<int> vi(j+1);
while(flag>=0){
if(abs(nums[i])>abs(nums[j])){
vi[flag]=(nums[i]*nums[i]);
i++;
}
else{
vi[flag]=(nums[j]*nums[j]);
j--;
}
flag--;
}
return vi;
}
};
judge2

总结
  1. 对比第一种和第二种方法,两者时间的差别主要在于是否去寻找了分段点。显然,这一步操作的时间复杂度也是$O(n)$。
  2. 双指针的思想主要就是两个指针像两边移动或向中间靠拢,然后达到边界条件。

轮转数组

题目

给你一个数组,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

  1. 示例 1:输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4]
  2. 示例 2:输入:nums = [-1,-100,3,99], k = 2 输出:[3,99,-1,-100]
方法: 双指针,使用递归。为了这递归我想了好久,然而发现性能并不怎么样……。而且还在参数列表处额外加了一个默认参数,有点不讲武德……
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
void rotate(vector<int>& nums,int k,int pos=0){
int n=nums.size(),i=pos;
k=k%n;
if(k==0) return;
for(;i<n-k;i++)
swap(nums[i],nums[n+(i-pos)%k-k]);
if(i==n+(i-pos)%k-k) return;
rotate(nums,k-(i-pos)%k,n-k);
}
};

解释:两个指针,左指针一直往右移动,右指针在一个区域内循环移动,每一步都交换两指针指向的值。

judge