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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
/ t3 c# ]1 ]; c2 t: m难度中等
2 [4 P; A  ~1 d2 g, ?! Q给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
5 S, y: E, p9 [+ L$ i) `- u你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

* E$ x) M, F  {% ?' B6 X5 ?示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
8 \+ p! t  P* g: d示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
, d! o! ~# ^) U: C  R- p& t输出：[-1,-1]
# {4 r9 _: R1 V5 o  Z* s2 |5 v/ Q示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
: ?9 u$ r$ b3 N9 y# k0 F1
2
1 G0 o$ s7 V  X3 U% O! A( K1 ?; R3
4
$ R  ]* y& H% a0 m' d* Z6 v% U3 w' Y0 G5
6
7
8
: h6 f8 I  n* ^/ s9
提示：

0 <= nums.length <= 10(5)
-10(9) <= nums[i] <= 10(9)
& t# ^" ?8 ~4 O0 s% Qnums 是一个非递减数组
-10(9) <= target <= 10(9)
思路
* ?2 S  ?" x' ~4 f/ O$ w关键步骤，与二分查找不同
5 t1 }& O* J7 U6 u' J9 pif(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
target==nums[mid]时，不结束循环，继续进入
两个if可以同时进入，寻找界限
设置限制，防止mid-1,mid+1越界
代码
class Solution {
5 z0 s) T2 q' b3 Q9 T4 F- A. npublic:
    int left=-1,right=-1;
    vector<int> searchRange(vector<int>& nums, int target) {
8 S. w. i% J* Y: x! Z) T) M/ x        if(nums.size()==0)  return vector<int>{-1,-1};
        binary_search(nums,target,0,nums.size());
        return vector<int>{left,right};
2 m) _8 C/ {* d) R8 a8 F    }
    void binary_search(vector<int>& nums,int target,int l ,int r){
3 \9 e# h% w9 ?" Y2 J" Q5 h        int mid=(r-l)/2+l;
        //printf("%d-%d\n",l,r);
5 k4 f0 F& _0 ?: z. o        if(target==nums[mid]){
7 {7 U& Q. F$ m6 e0 W) C3 |            if(left>mid||left<0)  left=mid;
8 `8 F5 \& s$ q: v$ b            if(right<mid||right<0)   right=mid;
$ J, M' G6 d8 D- `+ t        }
        if(l>=r) return;
0 t% z, @; _: a        if(target<=nums[mid]&&mid-1>=0)  binary_search(nums,target,l,mid-1);
        if(target>=nums[mid]&&mid+1<nums.size())   binary_search(nums,target,mid+1,r);
    }
2 h) X! N0 J. ]7 G' L- l};

4 I' @' Z: @  T) i————————————————
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
8 t- V$ @$ E- t5 {. {* i) Z# e) ]

1 B: z4 D9 r2 S0 l  J, o1 z5 u; D