二分查找(非朴素)--在排序数组中查找元素的第一个和最后一个位置

?个人主页：Lei宝啊?

愿所有美好如期而遇

---

目录

本题链接?

输入描述

输出描述

算法分析

1.算法一：暴力求解

2.算法二：朴素二分算法

3.算法三：二分查找左右端点

3.1查找左端点

3.1.1细节一：循环条件

3.1.2细节二：mid的值

3.2查找右端点

解题源码?

---

本题链接?

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

输入描述

我们选择示例1，接口为vector<int> searchRange(vector<int>& nums, int target) ，向nums中写入非递减的数字，也就是说可以有多个重复的相同数字。

输出描述

由于nums中可能有多个值与target相等，所以我们需要记录这个区间的左端点和右端点，然后返回这个区间，如果找不到，则区间为[-1,-1]。

算法分析

1.算法一：暴力求解

直接从左到右扫描这个数组，通过begin和end变量来记录相等于target的起始位置和结束位置，找不到则返回[-1,-1]，时间复杂度为O(N)。

2.算法二：朴素二分算法

直接二分，如果寻找的target在nums中只有一个，那么时间复杂度为log(N)，但是如果有多个的话，我们还是需要去遍历mid的左边和mid的右边，如果整个数组所有值都与target相等，就相当于要遍历整个数组，时间复杂度仍然为O(N)，这里我们使用朴素二分算法仍然不是最优的。

3.算法三：二分查找左右端点

3.1查找左端点

我们可以将数组分成两个区间，以[5,7,7,8,8,10],target = 8为例，既然我们要找左端点，也就是最左边的那个8，所以我们将数组分成小于target的区间和大于等于target的区间，即[5,7,7]? ?[8,8,10]这两个区间。(lhs意为left side hand即左手边，rhs意为right side hand即右手边)

我们定义一个mid，mid = lhs + (rhs - lhs) / 2，并且有两种结果：

• 当nums[mid] < target ，lhs = mid + 1;
• 当nums[mid] >= target,?rhs = mid;

你可能会问，为什么rhs = mid, 按照我们朴素二分算法的理解，应该是rhs = mid - 1, 我们可以举个例子，如果说mid = 3,也就是上面最左边的8，那么再怎么样我们也无法找到左端点了。

同时按照我们上面的两种结果，我们也可以发现一个事实，就是rhs永远不会出他的区间，lhs是可以跨区间的，当lhs == rhs时，也就代表着循环结束了。

所以这就是全部了吗？当然不是，他还有其他细节，这些细节一但注意不到，就是一个接一个的死循环。

3.1.1细节一：循环条件

朴素二分算法循环条件是lhs <= rhs，那么我们这里也是这样吗？上面我们提过一个事实，就是说当lhs == rhs时就已经结束了，而且正好是我们的左端点，所以说我们不用再去判断相等的情况，你可能会说，碰巧罢了，你这是能找到结果，你要是找不到呢？如果nums里全部大于target呢？如果nums里全部小于target呢？那我们分三种情况:

• 
• 
• 

所以我们不需要判断lhs == rhs这种情况，因为我们上述三种情况就是本题的所有情况，而我们也证实了当lhs == rhs时就是我们的结果，要么找到，要么就找不到。

但是有人会犯倔，我嫌麻烦，还得想这么多东西，不就多判断一次嘛？我就用lhs <= rhs，?有问题吗？还是分三种情况，运气好点就不死循环。

所以我们循环条件也有两个细节：

• 细节一：无需判断lhs == rhs，因为此时已经是结果了。
• 细节二： 如果真的比较了，可能会死循环，在leetcode众多测试用例中，一定是错的。

3.1.2细节二：mid的值

我们上面直接让mid = lhs + (rhs - lhs) /?2; 可能你也没有思考为什么，可不可以，事实上，在查找左端点时这样正好可以，但是放在查找右端点上就是死循环，那么右端点mid怎么算？

mid = lhs + (rhs - lhs + 1) / 2;那么我们把这个用在左端点上看看效果。

我们可以发现：

• 选择第一种方式，mid的值偏向于左边下标
• 选择第二种方式，mid的值偏向于右边下标?

细节很多，不注意就死循环，但是我们不要死记硬背，要去理解，怎么样就死循环了，这才是我们该做的。

3.2查找右端点

查找右端点和查找左端点思路完全相同，只是有些细节不同，我们这里指出：

1. 区间的划分：大于target的区间的小于等于target的区间
2. mid的计算：mid = lhs + (rhs - lhs + 1) / 2;

剩下的就是一个模子了。?

解题源码?

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) 
    {
        
        vector<int> v(2,-1);
        if(nums.size() <= 0)  return v;

        //计算左端点
        int lhs = 0, rhs = nums.size() - 1, mid = lhs + (rhs - lhs) / 2;

        while(lhs < rhs)
        {
            //分区间
            if(nums[mid] < target) lhs = mid + 1;   //小于区间
            else  rhs = mid;                        //大于等于区间        

            mid = lhs + (rhs - lhs) / 2;
        }
        
        if(nums[rhs] == target) v[0] = rhs;

        //计算右端点
        lhs = 0, rhs = nums.size() - 1, mid = lhs + (rhs - lhs + 1) / 2;

        while(lhs < rhs)
        {
            //分区间
            if(nums[mid] > target) rhs = mid - 1;   //大于区间
            else  lhs = mid;                        //小于等于区间        

            mid = lhs + (rhs - lhs + 1) / 2;
        }
        
        if(nums[rhs] == target) v[1] = rhs;

        return v;
    }
};