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

2023-12-30 18:52:04

?个人主页: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;
    }
};

文章来源:https://blog.csdn.net/m0_74824254/article/details/135306648
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。