说到二分查找算法，我们常常会想到用一个排序过的数组，但是其实二分查找不只能在有序数组中carry，只要观察出规律，很多情况都可以用二分思想快速解决问题，想要熟悉并且用好二分查找算法的思想，这篇文章已经够了。
第一题
这道题和我们的算法思想叫做同一个名字，所以这道题是了解二分查找算法首选的一道题，我想很多人都已经了解过了二分查找算法。
因为是有序数组，所以每次都能排除从中间位置查找都能够舍去一半的可能性，所以查找的时间复杂度只需要logn即可，如果从头到尾就需要O(N)的时间复杂度。
一个优化点
求mid时，可以这样用来防止溢出
一个小技巧
我们在选取mid时，如何判断怎么走left和rigth，相遇时才不会出现死递归的情况呢？
证明的话比较复杂，我们只需要记住，下边是很重要的，后边的题目都会用到。
上边右边的情况应该是right=mid-1;
而且一般需要left停在我们想要的位置，所以判断条件left位置应加上等于，会在下边的题解中提到。
举一个例子
上边求mid的式子，主要是为了防止溢出。
如果查找的过程中一直找不到关键字，那么直到left和right相遇后跳出循环，然乎判断相遇出的位置是否为我们要找的数字，如果不是就表示我们要找的数组中并没有这个值，如果找到就返回left（下标）
呐，暴力解法
再来看二分查找
代码如下
int search(vector<int>& nums, int target) { int left=0,right=nums.size()-1,mid=left+(right-left)/2; while(left<right) { if(nums[mid]<target) { left=mid+1; } else { right=mid; } mid=left+(right-left)/2;//这是取中若是奇数就直接用的情况。 } if(nums[left]!=target) { return -1; } return left;
下边是相加和为奇数，除以2得到结果加1的情况。
class Solution { public: int search(vector<int>& nums, int target) { int left=0,right=nums.size()-1,mid=left+(right-left+1)/2; while(left<right) { if(nums[mid]<=target) { left=mid; } else { right=mid-1; } mid=left+(right-left+1)/2; } if(nums[left]!=target) { return -1; } return left; } };
大家可以比较一下区别，也可以在本子上画一画这是如何控制相遇时不会死循环的。
第二题
这还是一道二分查找题，逻辑稍微复杂一点，还是练习我们的代码实现能力。
就像第一个例子，在数组中查找8，我们有两种思路，先找到左边的元素，然后找右边的元素，然后锁定右边的元素，直接查找左边的元素。另一种思路就是反过来。
当然，在找到一端的位置后，就使用一个变量保留该位置，然后继续使用二分查找寻找另一端的位置。
左端和右端不同的是该值大于前边的值或者是小于后边的值。
上边所说的很容易理解，接下来我们就开始写代码了。
class Solution { public://我想知道简便方法 vector<int> searchRange(vector<int>& nums, int target) { // 处理边界情况 if(nums.size() == 0) return {-1, -1}; int begin = 0; // 1. ⼆分左端点 int left = 0, right = nums.size() - 1; while(left < right) { int mid = left + (right - left) / 2; if(nums[mid] < target) left = mid + 1; else right = mid; } // 判断是否有结果 if(nums[left] != target) return {-1, -1}; else begin = left; // 标记⼀下左端点 // 2. ⼆分右端点 left = 0, right = nums.size() - 1; while(left < right) { int mid = left + (right - left + 1) / 2; if(nums[mid] <= target) left = mid; else right = mid - 1; } return {begin, right}; } };
要注意细节问题，就比如这道题的长度，如果第一次查找size=0就直接返回-1,-1，还有就是第一次查找如果没有查找到就直接返回-1,-1。
第三题
这道题目就不是在数组有序的情况下来完成的，使用二分查找我们要找到一定的规律就可以，来解析这道题
使用二分查找法，如果查找到3的位置，可以发现3是大于左边的0，小于右边的7，如果查找到2，他就是小于左边的，大于右边的，根据这个特性，我们就还是可以使用二分查找算法来完成这道题。
class Solution { public: int peakIndexInMountainArray(vector<int>& arr) { //寻找山峰位置的元素 int left=0,right=arr.size()-1; int mid=0; while(left<right) { mid=left+(right-left)/2; if(arr[mid]<arr[mid+1]) { left=mid+1; } else { right=mid; if(arr[mid]>arr[mid-1]) { return mid; } } } return -1; } };
这道题就是前边我们所说，二分查找并不是只有在数组有序的情况下才能使用的，只要我们发现需要查找的对象中元素是否有某种规律，我们就可以使用二分查找迅速来解决问题。
第四题
这道题和前边的寻找峰值十分类似，我们不需要担心存在多个峰值，我们只需要寻找规律就可以了。
来画图观察一下规律
在这个曲线上随机选取某点，观察规律，思考如何快速找到峰值并且不会出现错误判断。
第一种情况就是右边的值大于该点的值。
还有一种情况就是查找到的值右边小于该点的值，
这道题目要求的是返回任何一个峰值元素就可以，所以我们就不用考虑这么多，接下来就可以上手写代码了。
class Solution { public: int findPeakElement(vector<int>& nums) { if(nums.size()==1)//如果只有一个元素，那就直接返回0 { return 0; } int left = 0, right = nums.size() - 1; int mid = 0; while (left < right) { mid = left + (right - left) / 2; if(nums[mid]<nums[mid+1])//下边两种请况 { left=mid+1; } else { if(mid==0||nums[mid]>nums[mid-1]) { return mid; } else { right=mid; } } } return left; } };
二分查找不只是可以在数组中查找某值或者某特殊位置，在别的问题中使用也能达到很不错的效果。
第五题
这道题同样不是一个有序数组，而是一个半有序数组，但是我们还是可以用二分查找的思想来解决它。
还是找规律
当然还有一种情况，当数组旋转次数和数组元素一样，此时数组还是一个升序数组，这种特殊情况我们也可以判断。
首先说一下思路
还是定义一个left和一个right，当mid位置的元素大于第一个元素时，表明在第一个区间，就将left改到mid加1的位置，如果小于，就将right更新到mid的位置。当left和right相遇时就得到了正式答案。
当然有可能是一个升序数组，这样会一直向后更新left，相遇时就到达了最后一个元素，此时0位置的元素才是我们想要的结果，返回0就可以。
代码如下
class Solution { public: int findMin(vector<int>& nums) { int left=0,right=nums.size()-1; int mid=0; int flag=nums[0]; while(left<right) { mid=left+(right-left)/2; if(nums[mid]>=flag) { left=mid+1; } else { right=mid; } } cout<<left; if(nums[left]==nums[nums.size()-1]&&nums[left]>nums[0]) { return nums[0]; } return nums[left]; } };
第六题
这道题目不允许使用内置函数和运算符，暴力解法的话，只需要在0到x间不断循环，直到找到一个数的平方刚好小于等于x;
另一种解法就是二分查找
这道题还不能用我们上边的判断left最后位置的方法
if(mid*mid<x) { left=mid+1; }
如果用这种方法的话，在平方刚好小于x的位置上还会继续向后移动，所以我们选择另外一种。
if(mid*mid<=x) { left=mid; }
这样left所在位置的平方和就刚好是最近的小于等于x的。
代码如下
class Solution { public: int mySqrt(int x) { if(x==0) { return 0; } int left=1,right=x; while(left<right) { long long mid=left+(right-left+1)/2; if(mid*mid<=x) { left=mid; } else { right=mid-1; } } return left; } };
这道题如果mid不用long long就会超出int的范围，以至于不能通过全部用例。本题结束。
