首页 > 代码库 > leetcode 二分查找 Search for a Range
leetcode 二分查找 Search for a Range
Search for a Range
Total Accepted: 21480 Total Submissions: 78454My SubmissionsGiven a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm‘s runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].
题意：在一个排好序的数组，找给定值的起始下标和结束下标
思路：二分查找
先用lower_bound找到起始下标
再用upper_bound找到结束下标
lower_bound和upper_bound的实现参见《stl源码剖析》
复杂度：时间O(log n) 空间O(1)
vector<int> searchRange(int A[], int n, int target){
int l = distance(A, lower_bound(A, A + n, target));
int u = distance(A, upper_bound(A, A + n, target));
vector<int> res;
if(A[l] != target){
res.push_back(-1);
res.push_back(-1);
}else{
res.push_back(l);
res.push_back(u - 1);
}
return res;
}leetcode 二分查找 Search for a Range
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。