题目链接:Search for a Range
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].
这道题的要求是在一个有序数组中,找到给定的target在数组中出现的起止位置。如果不存在,返回[-1, -1]。要求时间复杂度O(logn)。
由于要求O(logn)的时间复杂度,可以考虑采用二分搜索。可以先二分搜索,找到target出行的某个位置,然后再以该位置为中心向两边遍历,直到边界或者不等于target。不过这样最差情况下,时间复杂度为O(n)。
既然二分查找可以找到元素,那么也可以进而找到边界。两次二分搜索,分别找到左边界和有边界(即target和A[m]相等时不中断查找)。
时间复杂度:O(logn)
空间复杂度:O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution
{
public:
vector<int> searchRange(int A[], int n, int target)
{
int l1 = 0, r1 = n - 1, m1;
while(l1 <= r1)
{
m1 = (l1 + r1) / 2;
if(target <= A[m1])
r1 = m1 - 1;
else
l1 = m1 + 1;
}
int l2 = 0, r2 = n - 1, m2;
while(l2 <= r2)
{
m2 = (l2 + r2) / 2;
if(target >= A[m2])
l2 = m2 + 1;
else
r2 = m2 - 1;
}
if(l1 <= r2)
return vector<int>{l1, r2};
else
return vector<int>{-1, -1};
}
};