题目

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

• 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

 

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

 

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

题解

数组是有序的，所以我们可以使用二分查找，先找到target值的下标，

找到下标之和，因为元素可能重复，所以会存在一个区间 

[target,...,target]

区间内有不定个target，当我们找到当前的下标 mid 时，就分别往前和往后查找，

找到第一个值不等于 target 的下标，在返回的时候，就对于 加一和减一

 

 1 class Solution {
 2 public:
 3     vector<int> searchRange(vector<int>& nums, int target) {
 4         int l=0;
 5         int r=nums.size()-1;
 6         
 7         while(l<=r)
 8         {
 9             int mid=(l+r)/2;
10             if(nums[mid]==target)//找到target，接下来找出区间[target,...,target]
11             {
12                 int k=mid-1;
13                 while(k>=l)//往前找[target,...,target]
14                 {
15                     if(nums[k]!=nums[mid])
16                         break;
17                     k--;
18                 }
19                 
20                 int k2=mid+1;
21                 while(k2<=r)//往后找[target,...,target]
22                 {
23                     if(nums[k2]!=nums[mid])
24                         break;
25                     k2++;
26                 }
27                 return {k+1,k2-1};
28             }
29             if(nums[mid]>=target)//往左找target
30                 r=mid-1;
31             if(nums[mid]<target)//往右找target
32                 l=mid+1;
33         }
34         return {-1,-1};
35     }
36 };