Search for a Range
Total Accepted: 21480 Total Submissions: 78454My Submissions
Given 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
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
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; }