1、二分查找题型要求
带查找的数组有序或者部分有序要求查找时间复杂度 l o g ( n ) log(n) log(n)
2、二分查找关键三问
left
精确二分查找模板（不保留 m i d mid mid在区间）
例如给定有序数组 [ 1 , 3 , 5 , 6 , 9 , 13 ] [1,3,5,6,9,13] [1,3,5,6,9,13]，查找数字 5 5 5 的下标代码如下：
int BinarySearch(int [] nums,int key){
int len = nums.size();
int left = 0;
int right =len-1;
int mid = -1;
while(left<=right){ //允许left、right、mid三者指向一个元素
mid = left + (right-left)/2;
if(nums[mid] == key){ //非常重要的判断条件
return mid;
}else if(nums[mid]
查找左/右边界模板(保留mid的情况)
给定有序数组
[
1
,
3
,
3
,
3
,
9
,
13
]
[1,3,3,3,9,13]
[1,3,3,3,9,13]，例
1
1
1 查找数字
3
3
3 首次出现的下标，例
2
2
2 查找
3
3
3数组最后一次出现的下标，如果直接套用上面的代码则会查找任意一个
3
3
3。 使用二分的思维来思考此问题，首先mid的判断条件完全不是上题的nums[mid] == key，因为就算找到这个mid也无法保证是最左边的，
本题在while循环中没有判断终止条件，完全靠while()中的判断终止，这里千万注意left 代码如下：
//=========================================左区间查找=================================================
int BinarySearch(vector nums,int key){
int len = nums.size();
int left = 0;
int right =len-1;
int mid = -1;
while(left=key){
right = mid; //往右折半,因为有等于的可能，所以包含 mid 在里面，不能 right = mid + 1 跳过mid
}else{
left = mid+1; //往左折半，这里可以判断出mid一定不是我们要的，所以可以跳过，让然也可以写成 left = mid 。
}
}
return left;
}
//=========================================右区间查找=================================================
int BinarySearch(vector nums,int key){
int len = nums.size();
int left = 0;
int right =len-1;
int mid = -1;
while(left 左边界二分查找 2
左边界查找的第二种类型用于数组部分有序且包含重复元素的情况，这种条件下在我们向左收缩的时候，不能简单的令 right = mid，因为有重复元素的存在，这会导致我们有可能遗漏掉一部分区域，此时向左收缩只能采用比较保守的方式，代码模板如下：
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
} else {
right--;
}
}
return nums[left] == target ? left : -1;
}
}
例题：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/
查找左右边界
只需要分别查找左边界和右边界就可以，代码如下：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[]{-1, -1};
if(nums == null || nums.length == 0) return res;
// find the left-end
int left = 0;
int right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1);
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
res[0] = nums[left] == target ? left : -1;
// find right-end
if (res[0] != -1) {
if (left == nums.length - 1 || nums[left + 1] != target) {
res[1] = left;
} else {
right = nums.length - 1;
while (left < right) {
int mid = left + ((right - left) >> 1) + 1;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
res[1] = right;
}
}
return res;
}
}
例题：https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
总结为如下表，其实不需要死记硬背，重在理解！再来一遍理解，当left<=right时，都需要 mid +1或者 mid-1 。如果判断条件是left < right 则若
left = mid则向上(右)取整 , (left + right) / 2 + 1; 否则 right = mid时，向下(左)取整(left + right) / 2 。
查找方式 循环条件 左侧更新 右侧更新 中间点位置 返回值 标准二分查找 left <= right left = mid - 1 right = mid + 1 (left + right) / 2 -1 / mid 二分找左边界 left < right left = mid - 1 right = mid (left + right) / 2 -1 / left 二分找右边界 left < right left = mid right = mid - 1 (left + right) / 2 + 1 -1 / right
至此，二分查找的所有内容基本上介绍完毕，后续见到了其他类型再做补充！
精准查找细节处理案例1
LeetCode 33题 点击查看题目！
此题为部分有序的题型，其实二分查找并不需要全部有序，只需要能够判断丢弃一半的数组的条件出现即可。本题的判断条件是查找有序的一半数组，因为有序的一半一定会尾部大于首部，nums=[9,11,7,8,9] ,nums[mid]=7, 因为nums[right]=9>=nums[mid] 所以右边有序，我们只需要在有序的一半里面查找是否target大于这部分有序的首部并且小于它的尾部即可。但是此题说起来简单，细节确实无比的复杂，必须考虑到nums若只有一个或者两个元素怎么办！若只有一个元素，那么这个元素是有序的吗？等等，请先看到此处自行实现代码再接着往下看代码实现：
class Solution {
public:
int search(vector& nums, int target) {
int len=nums.size();
int left=0;
int right=len-1;
int mid=-1;
while(left<=right){ //记得这是精确查找类题目，要保证left、right不能直接等于mid
mid=left+(right-left)/2;
if(nums[mid]==target)
return mid;
//查找有序的一半区间，看看是否需要舍弃，千万注意是>= 还是 > ，非常重要要想清楚，不然很难！
else if(nums[mid]>=nums[left]){
//左边有序
if(nums[mid]>=target && target>=nums[left]){
//target在左边
right=mid-1;
}else{
left=mid+1;
}
}else if(nums[mid]<=nums[right]){
//右边有序
if(nums[mid]<=target && target<=nums[right]){
//target在右边
left=mid+1;
}else{
right=mid-1;
}
}
}
return -1;
}
};
