二分搜索
文章目录
1、搜索旋转排序数组&在排序数组中查找元素的第一个和最后一个位置
题目
分析
①目标明确
②另一种思路：排除法
③避免死循环
总结
复杂度
2、旋转数组的最小数字
题目
分析
复杂度
3、寻找重复数
题目
分析
复杂度
4、先序/后序遍历构造二叉树
题目
分析
复杂度
5、寻找两个正序数组的中位数
题目
分析
6、寻找峰值
题目
分析
复杂度
7、搜索二维矩阵I&II
题目
分析
复杂度
复杂度
8、数组中的逆序对
题目
分析
1、搜索旋转排序数组&在排序数组中查找元素的第一个和最后一个位置
题目
在这里插入图片描述
在这里插入图片描述
分析
这题很明显是需要使用二分法的，这里顺便将二分法的使用做下总结。
①目标明确
使用二分法的步骤不外乎找到左右端点，然后取中间端点，再根据情况将左或右端点变成中间端点。这里一定要先理清什么情况将左端点变为中间端点，什么情况将右端点变为中间端点。
②另一种思路：排除法
这里是对mid划分的标准改一下，划分后一部分一定不存在目标元素，而另一部分可能存在目标元素（这里这样做是因为有的题目可能并不一定是要你找某个特定的元素）。如下图所示
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
使用上述解法，最后left是符合标准的最后一位的解（见题目：在排序数组中查找元素的第一个和最后一个位置）。
同理，如果是找第一个位置就可反过来，让mid落在left，同时每次迭代让left+1.
③避免死循环
如上图3（2）中所示，在循环至最后两个数时可能会发生死循环。
之所以会死循环，是因为，条件使得mid一直等于left，而left也不会向right那样写成mid+1，因为这里我们是将区域严格的分为了[left,mid-1]和[mid,right]两个部分，如果同时写left=mid+1，right=mid-1的话就会把mid给pass掉。
这里的解决方案是，令
mid=left+(right-left+1)/2
1
这样就能使mid每次都向上去整。
这样做的另一个好处是我们刻意使left向目标数上靠拢，最后的输出值可以直接选left。
总结
这里以33为例：
第一步，找mid，注意这里把区间分成了[left,mid-1]和[mid，right]两部分，这里除非left==right（事实上因为while的条件是left<right，所以这种情况不会发生），mid的取值永远是在left的右边。
int mid = left + ((right - left + 1)>>1);
1
第二步，判断是在mid和right是否在旋转点的同一侧，代码如下：
int search(vector<int>& nums, int target) {
int n=nums.size();
if(n==0) return -1;
int left=0,right=n-1;
while(left<right){
int mid=left+((right-left+1)>>1);
//当满足下面情况时，mid和right均在旋转点的同一侧，或者他们直接就都位于旋转点上面
if(nums[mid]<=nums[right]){
//满足下面情况，表示目标点在[mid,right]的范围内
if(target>=nums[mid]&&target<=nums[right]) left=mid;
else right=mid-1;
}
//mid和right是否在旋转点的异侧
else{
//满足下面情况，表示目标点在[left,mid)的范围内
if(target<nums[mid]&&target>=nums[left]) right=mid-1;
else left=mid;
}
}
return (nums[left]==target)?left:-1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
复杂度
