[TOC]
有序数组的查找问题
- 题目线索：排序数组 问题是“找” “查找” “寻找” “搜索”
- nums[mid]与谁进行比较
- = < >之后left 或 right的移动情况
- 终止情景分析，返回l还是r 一般情况下观察left==right时下一步游标的移动情况
结果一共有四种不同的返回方式：
- true or false
有无重复元素的区别在于？好像没什么区别，算法都是一样写
- 无重复元素：index or -1
如果有重复元素的话，结果将会不唯一
- 有重复元素：minIndex or -1
- 有重复元素：maxIndex or -1
前两种代码结构一模一样
int binarySearch(vector<int> &nums){
int left = 0;
int right = nums.size()-1;
while(left<=right){
int mid = left + (right-left)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]>target){
right = mid-1;
}
else if(nums[mid]<target){
left = mid+1;
}
}
return -1;
}对于基本二分法，当找到target时，代码并不会跳出while循环，而是直接在循环内返回，也就是说，跳出while循环就说明一定灭有找到target。
但是对于其他衍生类型的二分法，无论结果怎样，都会跳出while循环
首先，明确[left,right]范围绝对是正确的，算法从来不会把正确答案排除在区间之外。
受到旋转数组题目的启发，在普通二分查找中
只有跳出while循环，才能够真正找到该边界，因此需要正确处理找不到元素的情况。
对于寻找左侧边界，当nums[mid]=target时，我们理所应当地应该缩小右边界的值，但常规想法是right=mid，因为我们也不确定mid是否就是左边界，因此不敢忽略这个点。
但问题是这样写会导致循环在left==right时陷入无限循环，因此我们必须得做点什么，打破僵局，跳出循环。
对于while(left<=right)的左闭右闭写法，游标移动 left=mid或right=mid是危险的操作，使用一定要仔细斟酌。看看left=mid-1或right=mid-1是否可以
我们还可以这样分析：
假设mid处的值就是左边界，那么如果nums[mid]==target时，left一定也在mid处
找不到target的三种情况：
①target小于数组范围
②target大于数组范围
③target在数组范围内，但是并不存在
对于这三种情况，我们需要分析while循环结束后，left和right的分布情况。根据left和right的特点，进行条件判断和处理。
int findLeftEdge(vector<int> &nums,int target){
int left = 0;
int right = nums.size()-1;
while(left<=right){
int mid = left + (right-left)/2;
if(nums[mid]>=target){
right=mid-1;
}
else{
left=mid+1;
}
}
if(nums.size()==0) return -1;
if(left>nums.size()-1 || nums[left]!=target){
return -1;
}
else{
return left;
}
}
//////////////////////////////////////////////////
int findRightEdge(vector<int> &nums,int target){
int left = 0;
int right = nums.size()-1;
while(left<=right){
int mid = left +(right-left)/2;
if(nums[mid]<=target){
left = mid+1;
}
else{
right = mid-1;
}
}
if(nums.size()==0) return -1;
if(right==-1 || nums[right]!=target){
return -1;
}
else{
return right;
}
}int sqrt(int x)
给定n-1个元素的升序数组，找出其中缺失的0~n-1中的某个数
二分法寻找元素的左侧边界和右侧边界
基本分为两类
- 搜索某个target是否存在 代表题型81
- 搜索数组最小值 代表题型154
衍生出来的问法：
数组有可能有重复元素，或者不含重复元素
衍生问法一定要以基本题型为蓝本做答，据其实际情况对代码做出符合实际情况的微小修改
所有形式的旋转到最后都会呈现两种状态： 出现两个递增区间或者仅有一个递增区间。在对旋转数组使用二分法时，要时刻注意自己所描述的算法能否对两种形式的数组均生效。
81题和154题就是很好的例子。在154题中，当nums[mid]与nums[left]进行比较后，两种形式的数组会产生不同的推断结果，但与nums[right]比较就不会。因此我们在154题中放弃nums[mid]与nums[left]的比较，转向使用nums[right]
将nums[mid] 与 nums[left] 或nums[right]进行比较的依据是：
通过这种比较，我们可以确定mid的其中一侧是单调的。
但是对于154题来说，当nums[mid]与nums[left]比较时，确定一侧
对于true or false类型题目，有无重复元素感觉并不影响，因为能找到就可以了
但是对于index or -1类型题目，如果数组有重复元素，得到答案将不会统一
对于minindex or -1/maxindex or -1，数组必须允许有重复元素，否则讨论这类题目就没什么意义了。
给定可能含有重复元素的旋转数组nums和target，判断target是否在nums中出现：返回true or false
==与基本二分法的结构一致==
nums[mid]可以和nums[right]或者nums[left]比较
可能有重复元素给算法带来的变化：
与81给定条件相同，但是数组中的值互不相同。返回值为index or -1
给定可能含有重复元素的旋转数组nums和target，返回target在数组中的索引最小值，若没有找到，返回-1
==同样是寻找target的题目，81和10.03完全可以用一套模板解决。模板的核心思想是比较nums[mid]和区间端点的大小关系，从而能够判断mid和其端点之间的位置关系和某侧的单调性。==
给定可能含有重复元素的旋转数组nums，搜索数组的最小值
给定不含有重复元素的旋转数组nums，搜索数组的最小值
与154相比的变化：
由于单调，因此不存在nums[mid]=nums[right]的情况
但同样的: right=mid的原地踏步情况此时也需要被处理。在此前，原地踏步的情况是在nums[mid]==nums[right]条件分支中被解决的。
现在，由于不存在重复元素，因此当闭合区间只剩一个元素的时候，该元素就是我们要找的最小值。