1.二分查找介绍
使用二分查找必要条件:数组中的元素是单调的
二分查找--时间复杂度 O(logn)，小于暴力搜索O(n)。
但我们使用二分查找时会遇到很多一看就会，一做就废的问题。
比如：你是否真正理解了为什么 写while(left<=right)而不是while(left<right)
又或者，你是否真正理解了为什么 left=mid+1,而不是left=mid，反之亦然。
如果你没有搞懂这些，只能说明你对二分查找算法的理解不够透彻
2.二分查找的三类情况
(1) 左闭右闭区间 [a,b]
在这里我们让 left=a,right=b,可以写while(a<=b)。
为什么？
我们可以这么理解，在左闭右闭区间中，a=b是合法的，如[1,1]是合法的
下面展示一下左闭右闭区间的代码实现，采用的是力扣风格的代码
#include<bits/stdc++.h> using namespace std; int binary_Search(vector<int>& nums,int target) { int len = nums.size(); int left = 0; int right = len-1; while(left<=right) { int mid = left+(right-left)/2; if(nums[mid]>target) { right = mid-1; } else if(nums[mid]<target) { left = mid+1; } else { return mid; } } } int main() { int a[5] = {1,4,6,8,3}; vector<int>v1(a,a+5); int target = 8; cout<<binary_Search(v1,target); }
接下来会有朋友疑惑，为什么left=mid+1,我明明看到有的代码写的是left=mid，接下来给大家解释：因为不管是left还是right，因为两边都是闭区间，所以left和right都是可以取得到的，那么在查找的过程中已知了mid这个值是不符合条件的，那么我们就不需要下次查找的时候再将mid算进来了，否则会显得很冗余
(2)左闭右开区间 [a,b)
同上，我们让 left=a,right=b，请大家先行思考，我们此时可不可以写while(left<=right)了呢？
答案是：万万不可，因为右边是开区间，a=b是不合法的，比如：[2,2)是不合法的，因为右边的2是取不到的
int binary_Search(vector<int>& nums,int target) { int len = nums.size(); int left = 0; int right = len; //在实际数组中，nums[len]是取不到的，在这里我们当作开区间处理 while(left<right) { int mid = left+(right-left)/2; if(nums[mid]>target) { right = mid; } else if(nums[mid]<target) { left = mid+1; } else { return mid; } } return -1; } int main() { int a[5] = {1,4,6,8}; vector<int>v1(a,a+4); int target = 8; cout<<binary_Search(v1,target); }
到这里可能又有人想问了，为什么这里right=mid而不是right=mid-1,因为右边是开区间，我们是取不到的，所以使right=mid时，也没有取到mid，所以这里的right=mid等效于上面左闭右闭区间中的right=mid-1。
(3) 左开右闭区间 (a,b]
通过上述两种情况，第三种情况与第二种情况正好是相反的关系，在这里就不做多余的介绍了，因为左开右闭区间的二分查找算法 在很多工程中不被使用，大多使用上述两大类情况
