【LeetCode】二分查找
2024-08-20 16:46:54
给一个升序数组,找到目标值在数组中的起始和结束位置,时间复杂度为 O(log n)。
e.g.
给定数组 [5, 7, 7, 8, 8, 10] 和目标值 8,返回 [3, 4]。若目标值不在数组中,返回 [-1, -1]。
我使用最死的二分查找,分别搜索起始和结束位置。这种思路也可以使用递归实现。
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> result = {-, -};
int low = , high = nums.size() - ;
while (low <= high) {
// 二分查找使用 mid = (high + low) / 2 可能溢出
int mid = low + ((high - low) >> 1);
if (nums[mid] == target) {
if (result[] == -) {
if (mid == || nums[mid] != nums[mid - ]) {
result[] = mid;
low = , high = nums.size() - ;
}
else
high = mid - ;
} else {
if (mid == nums.size() - || nums[mid] != nums[mid + ]) {
result[] = mid;
break;
}
else
low = mid + ;
}
}
else if (nums[mid] > target)
high = mid - ;
else if (nums[mid] < target)
low = mid + ;
}
return result;
}
C++ STL中自带一些使用二分查找实现的算法,
#include <algorithm>
pair<forward_iterator,forward_iterator> equal_range( forward_iterator first, forward_iterator last, const TYPE& val );
pair<forward_iterator,forward_iterator> equal_range( forward_iterator first, forward_iterator last, const TYPE& val, CompFn comp );
函数 equal_range 返回非递减序列 [first, last) 区间中等于 val 的元素区间,返回值是一对迭代器 i 和 j 。i 是 val 可插入的第一个位置(即lower_bound),j 是 val 可插入的最后一个位置(即upper_bound),equal_range 可以被认为是 lower_bound 和 upper_bound 的结合。
(lower_bound 在 [first, last) 区间进行二分查找,返回大于等于 val 的第一个元素位置。如果所有元素都小于 val,则返回 last 的位置。
upper_bound 在 [first, last) 区间进行二分查找,返回大于 val 的第一个元素位置)
因此以下代码可直接得出结果。
vector<int> searchRange(vector<int>& nums, int target) {
auto bounds = equal_range(nums.begin(), nums.end(), target);
if (bounds.first == bounds.second)
return {-, -};
return {bounds.first - nums.begin(), bounds.second - nums.begin() - };
}
vector<int> searchRange(vector<int>& nums, int target) {
int lo = lower_bound(nums.begin(), nums.end(), target) - nums.begin();
if (lo == nums.size() || nums[lo] != target)
return {-, -};
int hi = upper_bound(nums.begin(), nums.end(), target) - nums.begin() - ;
return {lo, hi};
}
最新文章
- 三种观察者模式的C#实现
- Logging configuration
- MongoDB安装,配置
- virtualtree 的使用(Delphi)
- URL中文乱码处理总结(转)
- OPencv1.0配置vs2010(介于OPencv的经典之作。都是OPencv1.0为基础的。)
- 教你如何在word中像LaTex那样打出漂亮的数学公式
- 如何在openlayer接入矢量数据
- Hibernate系列学习之(二) 多对一、一对一、一对多、多对多的配置方法
- mybatis关于ORM的使用以及设计(二)[DaoInterface 转换 Mapper代理对象]
- WebService CXF知识总结
- nginx ------反向代理和负载均衡
- shell脚本编写informix数据库中表的导入和导出
- 【ARC102E】Stop. Otherwise...(容斥原理,动态规划)
- ARMV8 datasheet学习笔记1:预备知识
- kali linux 数据库分析工具简述
- 0-MAVEN SETTING
- mac home目录创建文件夹,修改权限
- SSH三大框架的关系、使用到的jar包、配置文件图解
- Service生命周期以及应用