二分查找及模板深度解析：right ＜= left 还是 right ＜ left ? mid=left+(right-left)/2还是mid=left+(right-left +1 )/2 ?

@[TOC](二分查找及模板深度解析：right <= left 还是 right < left ? mid=left+(right-left)/2还是mid=(left+right-left)/2 ?)

前言

下面博主会给出一道经典面试题进行分析，在最后会给出二分查找模板！！！

题目：

1. 解读

我们可以将题目转化为求target第一次出现的下标，以及最后一次出现的下标。然后就转换成两次二分查找了，分别查找左右边界了！

2. 二分查找左边界

大概思路已经了，下面就是判断循环条件是right <= left 还是 right < left？ 以及中点求取是 mid=left+(right-left)/2还是mid=left+(right-left +1 )/2 ?

2.1 循环判断条件

在上述循环中，我们得到了左右边界移动行为：left = mid + 1 和right = mid。

结论： 循环条件是right <= left 还是 right < left ，主要问题在于最后一步left=right是否会导致死循环。如果不会的,两者循环判断条件无所谓，任选其一即可。

2.2 中点求取

所以中点mid=left+(right-left)/2还是mid=left+(right-left +1 )/2，主要还是取决于左右下标行为在最后当数据为偶数（即2个）时是否会导致死循环。如果两种方式都不会，则两者任选其一。

但好在我们有模板，无需担心

3. 右边界

4. 最终代码

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)
            return {-1, -1};
        int begin=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;
        
        //一定存在结果，查找最后一个元素
        left=0, 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, left};
    }
};

5. 模板

模板一：三段式（最普通）

由于上述情况时过于简单，博主就不介绍了。

模板二：⼆段式

请⼤家⼀定不要觉得背下模板就能解决所有⼆分问题。⼆分问题最重要的就是要分析题意，然后确定要搜索的区间，根据分析问题来写出⼆分查找算法的代码。

要分析题意，确定搜索区间，不要死记模板，不要看左闭右开什么乱七⼋糟的题解

模板记忆技巧:

1. 关于什么时候⽤三段式，还是⼆段式中的某⼀个，⼀定不要强⾏去⽤，⽽是通过具体的问题分析情况，根据查找区间的变化确定指针的转移过程，从⽽选择⼀个模板。
2. 当选择两段式的模板时：
   ◦ 在求 mid 的时候，只有 right - 1 的情况下，才会向上取整（也就是 +1 取中间数）