题目描述
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
解法1：二分
思路：
1.两次二分，第一次二分找到最左边为目标值的索引，第二次二分找到最右边为目标值的索引
2.以找到左边目标值为例，如何找到最左边目标值
我们可以通过判断nums[mid]（以下简称mid）<target 找到最左边目标值，思考当mid <target 意味着 区间需要向右移动以使得mid值变大，当mid >=target 区间先左移动，若存在目标值，那么最后得到的必然是最左端的目标值，
3.后处理：先找到左边目标值，若左边目标值不存在，直接返回[-1,-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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
int n=nums.size();
vector<int> res;
if(n==0)
{
res.push_back(-1);
res.push_back(-1);
return res;
}
int first,second;
int left,right,mid;
left=0,right=n-1;
while(left<right)
{
mid=left+(right-left)/2;
if(nums[mid]<target)
left=mid+1;
else
right=mid;
}
if(nums[left]!=target)
{
res.push_back(-1);
res.push_back(-1);
return res;
}
first=left;
left=0,right=n-1;
while(left<right)
{
mid=left+(right-left+1)/2;
if(nums[mid]>target)
right=mid-1;
else
left=mid;
}
second=left;
res.push_back(first);
res.push_back(second);
return res;
}
};
|