基础算法--二分查找

什么是二分查找

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

二分查找的魅力所在

二分查找最大的优势就是效率高，它的时间复杂度是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;
            }
            else
                return 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;
    }
};