二分查找算法应用
🎈 作者:
🎈 简介:CSDN博客专家🏆,华为云享专家🏆,Linux、C/C++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
🎈 关注专栏:
(优质好文持续更新中……)🚀🎈 欢迎小伙伴们点赞👍、收藏⭐、留言💬
一、题目描述
给定一个按照升序排列的整数数组 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计算的是上界。
四、代码实现
五、复杂度分析
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++、云计算、物联网、面试、刷题、算法尽管咨询我,关注我,有问题私聊!
欢迎小伙伴们点赞👍、收藏⭐、留言💬
- 点赞
- 收藏
- 关注作者
评论(0)