网站是生成静态好还是动态好,网站开启gzip压缩,金环建设集团网站,上海网址导航文章目录 写在前面Tag题目来源题目解读方法一#xff1a;二分查找方法二#xff1a;使用库函数 知识回顾二分查找的三种写法与三个问题常用的二分库函数 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 文章目录 写在前面Tag题目来源题目解读方法一二分查找方法二使用库函数 知识回顾二分查找的三种写法与三个问题常用的二分库函数 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【数组】【二分查找】 题目来源
34. 在排序数组中查找元素的第一个和最后一个位置 题目解读
方法一二分查找
对于有序数组中搜索指定元素问题我们应该优先想到二分查找方法。题目有要求解法的时间复杂度必须为 O ( l o g n ) O(logn) O(logn)那本题基本确定需要使用二分查找法解题。
思路
我们只需要写出一个函数找出数组中 target 第一次出现的位置。使用二分查找轻松实现。还有一些实现细节见代码中的注释。
代码
class Solution {
public:// 【闭区间写法】找出 nums[i] target 的最小的 iint lower_bound(const vectorint nums, int target) {int left 0, right nums.size() - 1;while (left right) { // 区间不为空// 注意指针的指向变化int mid left ((right - left) 1);if (nums[mid] target) {left mid 1;}else {right mid - 1;}}return left;}vectorint searchRange(vectorint nums, int target) {int start lower_bound(nums, target);if (start nums.size() || nums[start] ! target) {return {-1, -1};}// 如果 start 存在那么 end 必定存在int end lower_bound(nums, target 1) - 1;return {start, end};}
};复杂度分析
时间复杂度 O ( l o g n ) O(logn) O(logn)。
空间复杂度 O ( 1 ) O(1) O(1)。
方法二使用库函数
对于上述手写二分查找的函数C 标准库中有对应的函数 lower_bound \texttt{lower\_bound} lower_bound 实现相同的功能。不论是库函数还是手写二分查找都需要掌握。
代码
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int start lower_bound(nums.begin(), nums.end(), target) - nums.begin();if (start nums.size() || nums[start] ! target) {return {-1, -1};}int end lower_bound(nums.begin(), nums.end(), target 1) - nums.begin() - 1;return {start, end};}
};知识回顾
二分查找的三种写法与三个问题
二分查找有三种写法闭区间、左闭右开和开区间写法无论是哪种写法始终都要关注三个问题
何时退出循环二分查找据此有了三种写法指针如何移动最后返回什么
关于以上三种写法与三个问题可以参考 【面试经典 150 | 二分查找】搜索插入位置。
常用的二分库函数 lower_bound(beg, end, val) \texttt{lower\_bound(beg, end, val)} lower_bound(beg, end, val) 返回一个迭代器表示 第一个不小于大于等于 val 的元素如果不存在这样的元素则返回 end 迭代器。 upper_bound(beg, end, val) \texttt{upper\_bound(beg, end, val)} upper_bound(beg, end, val) 返回一个迭代器表示 第一个大于 val 的元素如果不存在这样的元素则返回 end 迭代器。 equal_range(beg, end, val) \texttt{equal\_range(beg, end, val)} equal_range(beg, end, val) 返回一个 pair其 first 成员是 lower_bound \texttt{lower\_bound} lower_bound 返回的迭代器second 成员是 upper_bound \texttt{upper\_bound} upper_bound 返回的迭代器。 binary_search(beg, end, val) \texttt{binary\_search(beg, end, val)} binary_search(beg, end, val) 返回一个 bool 值指出序列中是否包含等于 val 的值。
以上每一个函数都提供一个第二版本这个版本可以自定义比较操作。
写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
