基础算法--二分查找

什么是二分查找

二分查找，也叫折半查找，是一种专门为有序数组量身定制的查找算法。想象一下，你走进了一家按编号顺序排列书籍的图书馆，要找某一本书，要是从第一本开始逐本翻找，那可得费不少时间。二分查找可就机灵多了，它先把书架一分为二，看看目标书籍在左边还是右边，然后果断舍弃不需要的那半边，接着在剩下的半边里继续对半分、再找，如此循环，快速锁定目标。

二分查找的魅力所在

二分查找最大的优势就是效率高，它的时间复杂度是O(logN) 。啥意思呢？就是随着数据量 n 不断增大，查找所需的时间增长得极为缓慢。与之相比，顺序查找的时间复杂度是O(N) ，数据量一大，顺序查找耗时就会蹭蹭往上涨。打个比方，在有 100 万本书的图书馆里找书，二分查找可能几十次对比就搞定，顺序查找说不定就得翻个几十万次。

一道简单的题目示例

1.二分查找

代码：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0,right = nums.size()-1;int mid = 0;while(left<=right){mid = left+(right-left)/2;//防止溢出if(nums[mid]<target){left = mid+1;}else if(nums[mid]>target){right = mid-1;}elsereturn mid;}return -1;}
};

2.在排序数组中查找元素的第⼀个和最后⼀个位置（medium）

这里也是用二分查找，只不过这里需要查找两个端点。

首先当我们查找左端点的时候,需要处理好细节，尤其是这里求中点的操作。必须是left+(right-left)/2，因为其实left = right的时候已经是最终结果了，走到最后情况就是两个数里面找中点，因为我们是找左端点mid会落到right的位置，如果这个时候mid也落在x>=t，那么right= mid，我们会发现right没有动，那么接下来就会进入死循环。但是当我们走left+(right-left)/2的时候，mid = left,无论是x<t还是x>=t都不会进入死循环，当x<t时，left = mid+1，这时就撞上了right停止循环，当x>=t时，right就更新为mid，这时会撞上left，也会停止循环。

那么右端点也同理，必须使用mid = left+(left-right+1)/2 ,当区间内还剩两个数时，mid当时必然会落在左边的数上，如果用第一个算，那么此时mid = left，如果这时x<=t的，则left又是等于mid，则left不变，这样就会进入死循环。

这里如果我们使用mid = left+(left-right+1)/2就不会进入死循环，因为这个时候mid会等于right，那么这个时候无论是走x<=t还是x>t都不会死循环，当x<=t的时候，更新left，left = mid，撞上right，循环截止，当x>t的时候，更新right，right = mid-1,right会撞上left,循环截止。

代码：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if(nums.size()==0) return {-1,-1};int begin = 0,end = 0;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;//二分右端点right = nums.size()-1;while(left<right){int mid = left+(right-left+1)/2;if(nums[mid]>target) right = mid-1;else left = mid;}return {begin,right};}   
};

总结二分模板：

3.x的平⽅根（easy）

题目非常的简单，但我们这里主要是学习使用二分查找，暴力解法也很容易想到，就是将0-x的所有数字平方遍历一遍。但我们这里要使用的是二分查找。

首先找一下二段性，直接看下图，ret就是要返回的目标值，ret的左边的平方一定是小于等于x的，4包含4左边的平方一定是小于17的，6的左边包含它自己会小于等于36。

那么这里就可以直接套用我们上一题总结的模板了：

class Solution {
public:int mySqrt(int x) {if(x<1) 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 right;}
};