leetcode刷题笔记数组系列（一）：一文解决二分查找及其衍生题

前言

二分查找的前提是数组为有序数组。leetcode中和二分查找相关的代表题目有：第704,34,35,367题，本文以这几题为例进行说明。

二分查找涉及的很多的边界条件，逻辑比较简单，但就是写不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle呢，还是要right = middle - 1呢？

大家写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。

我个人的习惯是写成左闭右闭区间，原因是个人感觉左闭右闭区间更容易理解。
下面以具体的题目进行说明：

一.经典二分查找：leetcode第704题

（题目我就不抄了，大家直接去leetcode看就行了）
给定升序数组，这题是典型的二分查找题目，没有任何变种衍生。

二、定义在左闭右闭区间的二分查找该如何写：

因为定义target在[left, right]区间，所以有如下三点：
（1）while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
（2）if (nums[middle] > target) 时当前区间的中间值比目标值大，故目标值在当前区间的左半边区间，所以需要修改right值，即有 right = middle-1,新的区间就是[left,middle-1]；
（3）同样道理 if(nums[middle]<target)时当前区间的中间值比目标值小，说明目标值在当前区间的右半区间，所以需要修改left值，即有left = middle+1,新的区间就是[middle+1,right];

所以，这题的代码就可以写成这样：

class Solution {
public:
    int search(vector<int>& nums, int target) {

        // 二分法 左闭右闭区间法 []
        int left = 0;   // 数组左下标
        int right = nums.size()-1;  // 数组右下标
        while(left<=right)
        {
            int middle = left+(right - left)/2; // 防止溢出
            if(nums[middle] == target)
                return middle;
            else if(nums[middle] > target)  // 目标在左半边,改变右区间
            {
                right = middle - 1;
            }
            else    // 目标在右半边，改变左区间
            {
                left = middle + 1;
            }
        }
        return -1;
    }
};

三、二分查找过程理解：leetcode第35题，当二分查找失败后…

这题和上面的题唯一的区别就是，如果目标值不在数组中，返回它将会被按顺序插入的位置：
这需要我们在纸上手动模拟一下二分查到的过程：

以示例2为例：在nums = [1,3,5,6]中查找2：
按照上面的逻辑：初始区间为[0,3]
第一次循环：middle=1,nums[1]为3且大于目标值2，故调整到左区间，区间变为[0,0]
第二次循环：middle=0,nums[0]为1且小于2，故调整到右区间，区间变为[1,0]
很明显，1>0不满足left<=right,需要跳出循环

至此，二分查找失败，但是二分查找失败仅仅说明是没有找到该元素，并不是没有意义的，意义就在于：如果目标值不在数组中，它将会被按顺序插入的位置就是此时的left下标所指之处。

所以，这题的代码如下：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if(target > nums[len-1])    return len;
        if(target < nums[0])    return 0;
            
        int left = 0,right = len-1;
        while(left<=right)
        {
            int middle = left+(right-left)/2;
            if(target > nums[middle])
            {
                left = middle+1;
            }
            else if(target < nums[middle])
            {
                right = middle-1;
            }
            else{
                return middle;
            }
        }
        return left;    // 将left指针处返回
    }
};

四、当有重复元素时的二分查找：leetcode第34题

无重复元素时的二分查找结果是唯一的，当有重复元素时，又该如何分析呢？

这题有了多个重复元素，让我们找出第一次和最后一次出现的位置，这该怎么分析呢？
采用这样的思路：原先的逻辑当target<nums[middle]时，需要到区间的左边去找，在此处增加一处逻辑，就是当target == nums[middle]时候，依然去区间的左边去找，看左边是否仍然有和target相同的元素，即寻找target值的左边界，这样查找结束之后如果找得到的话nums[left]就应该是target的左边界

以[5,7,7,8,8,8,8,8,10]寻找target=8为例进行说明：
一开始 区间为[0,8] middle=4,nums[middle]=8和target相等，此时因为不确定左边是否还有与之相等的，故继续朝左边找
区间变为[0,3] middle=1,nums[middle]=7小于8 朝右边找
区间变为[2,3],middle=2,nums[middle]=7小于8 朝右边找
区间变为[3,3],middle=3,nums[middle]=8等于8，按照刚才的逻辑，要继续朝左边找
区间变为[3,2],不满足left<=right,循环跳出，而最左边的边界就是nums[left]

同理可寻找右边界，不再赘述
代码如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {

        
        vector<int> ans(2,-1);
        if(0 == nums.size() || target > nums[nums.size()-1] || target<nums[0]) return ans;

        int left = 0,right = nums.size()-1;
       
        // 先找左边界
        while(left <= right)
        {
            int middle = left + (right-left)/2;
            if(nums[middle] >= target)
                right = middle - 1;
            else
                left = middle + 1;
        }
        if(nums[left] != target)    // 一个和target相等的也没有
        {
            // std::cout<<"["<<left<<"  "<<right<<"]   nums[left-1]:"<<nums[left]<<std::endl;
            return ans;
        }
        else ans[0] = left;

        // 再找右边界
        right = nums.size()-1;
        while(left <= right)
        {
            int middle = left + (right-left)/2;
            if(nums[middle] <= target)
                left = middle + 1;
            else right = middle - 1;
        }
        ans[1] = left-1;
        return ans; 
    }
};