二分查找算法应用

举报
Linux猿 发表于 2021/12/18 22:50:09 2021/12/18
【摘要】 CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊! 欢迎小伙伴们点赞👍、收藏⭐、留言💬


🎈 作者:Linux猿

🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

🎈 关注专栏:LeetCode面试必备100题 (优质好文持续更新中……)🚀

🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬


一、题目描述

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值 target,返回 [-1, -1]。

二、测试样例

输入:nums = [5,7,7,8,8,10], target = 8

输出:[3,4]

说明:在数组中, 只有两个 8 ,范围是 [3, 4]。

三、算法思路

从题目不难看出,应该向二分查找算法的方向思考,数组是按照升序排列,正好符合二分查找的前提条件。

那么,如何查找呢?

查找开始和结束位置,相当于查找目标值在数组中的下界和上界,所以可以直接采用 STL 中的算法 lower_bound 和 upper_bound 算法来求解。其中,lower_bound 计算的是下界,upper_bound计算的是上界。

四、代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int lt = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
        int rt = upper_bound(nums.begin(), nums.end(), target) - nums.begin();
        if(lt >= nums.size() || nums[lt] != target) return {-1, -1};
        return {lt, rt-1};
    }
};

int main()
{
    int a[] = {5,7,7,8,8,10};
    vector<int>nums(a, a+6);
    Solution obj;
    vector<int>ans = obj.searchRange(nums, 8);
    cout<<ans[0]<<" "<<ans[1]<<endl;
    return 0;
}

五、复杂度分析

5.1 时间复杂度

时间复杂度为:O(logn),在上述代码中,使用的是 STL 中的 lower_bound 和 upper_bound 函数,这两个函数使用的都是二分查找算法,一个查找下界,一个查找上界,其中,lower_bound 返回大于等于目标值的元素的指针,upper_bound 返回的是大于目标值的元素的指针。因为二分查找算法的时间复杂度为 O(logn),故上述算法总的时间复杂度为O(logn)。

5.2 空间复杂度

空间复杂度为:O(1),在上述代码中,仅仅使用到了两个变量 lt 和 rt,故总的空间复杂度为O(1)。

六、总结

本题主要考查二分查找算法的应用,当然,可以不使用 STL 中的函数,可以自行实现一下,加深理解。


CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!

欢迎小伙伴们点赞👍、收藏⭐、留言💬


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。