模型总结：二分查找

一、最基本的二分查找

[704. 二分查找]

通过对基本的二分查找的分析，我们可以总结变式的来源。

1.二分查找的应用场景

1.数组是有序的。

2.数组中的元素不重复。

所谓查找，==本质就是每一次排除一批数据==。因此往往也伴随着需要分类讨论。

2.二分查找核心书写思路

首先需要处理要查找的元素在数组范围外的部分，即没有找到。
然后在数组中进行二分查找。
[left,right]：区间为left和right，其中它们都是数组下标。
while(left<=right)：这是因为下标为left=right的这个数据还没有参与比较。
if(target<mid) left=mid+1：这是因为mid值已经参与比较了，而且使用的是闭区间。

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

二、变式一：元素可以重复

34. 在排序数组中查找元素的第一个和最后一个位置

1.思路

该变式没有完全改变有序的特性，依然是进行查找，因此还是可以使用二分查找的。

还是进行分类讨论，即先处理在数组之外的情况。
再在数组内部进行二分查找寻找左右边界。

寻找边界的关键在于，当每一次比较后的left和right如何进行处理。

这里以左边界为例：

当target<nums[mid]的时候，显然无论元素是否重复在mid的右边都没有target值，因此right=mid-1；

当target>nums[mid]的时候，显然无论元素是否有重复mid的左边都没有target值，因此left=mid+1；

当target=nums[mid]的时候，由于是寻找左边界，因此不关心mid右边是否有重复的值，但是左边依然有可能有重复的值，因此right=mid-1。

而最终while循环终止的时候，一定是right=left-1，所以right+1即left，就是左边界。

2.具体实现

class Solution {
public:
    int FindLeftBorder(vector<int>& nums,int target,int left,int right)
    {
        while(left<=right)
        {
            int mid=(right+left)/2;
            if(target>nums[mid])
            {
                left=mid+1;
            }
            else
            {
                right=mid-1;
            }
        }
        if(nums[right+1]==target)
        {
            return right+1;
        }
        else
        {
            return -1;
        }
    }
    int FindRightBorder(vector<int>& nums,int target,int left,int right)
    {
        while(left<=right)
        {
            int mid=(right+left)/2;
            if(target<nums[mid])
            {
                right=mid-1;
            }
            else
            {
                left=mid+1;
            }
        }
        if(nums[left-1]==target)
        {
            return left-1;
        }
        else
        {
            return -1;
        }
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> v;
        v.resize(2);
        if(nums.size()==0)
        {
            v[0]=-1;
            v[1]=-1;
            return v;
        }
        if(target<nums[0])
        {
            v[0]=-1;
            v[1]=-1;
            return v;
        }
        else if(target>=nums[0]&&target<=nums[nums.size()-1])
        {
            int left=0;
            int right=nums.size()-1;
            int rightborder=FindRightBorder(nums,target,left,right);
            int leftborder=FindLeftBorder(nums,target,left,right);
            v[0]=leftborder;
            v[1]=rightborder;
            return v;
        }
        else
        {
            v[0]=-1;
            v[1]=-1;
            return v;
        }
    }
};

3.思考

关键点就在于二分查找的最后结果是落在left=right的情况下，查找边界与简单的二分查找的区别就在于如何处理target=nums[mid]使得当最终left=right的时候，left或者right是一个边界。显然每一次都是对mid+1或者-1操作来缩小查找范围，可以从这里进行思考怎么处理。

三、变式二：非数组二分查找

69. x 的平方根

1.思路

思路主要在于，怎么识别它是一个二分查找。其实还是满足以上两个条件，即无重复元素，数组有序。

求x的平方根，即在x之前的数据中寻找x的平方根。

2.实现

class Solution {
public:
    int mySqrt(int x) {
        int left=1;
        int right=x;
        while(left<=right)
        {
            int mid=left+(right-left)/2;
            if(mid<(x/mid))
            {
                if(mid+1>(x/(mid+1)))
                {
                    return mid;
                }
                left=mid+1;
            }
            else if(mid>(x/mid))
            {
                if((mid-1)<(x/(mid-1)))
                {
                    return mid-1;
                }
                right=mid-1;
            }
            else
            {
                return mid;
            }
        }
        return 0;
    }
};

注意，这里要使用除法而不能是乘法，有可能出现越界的情况。同时为了避免越界，使用的是left+(right-left)/2的方式来寻找mid。