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

题目

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 };

 

上一篇:每日一练(24):在排序数组中查找数字


下一篇:第十四天155. 最小栈