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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
难度中等
  s, l$ r. Z9 l5 w给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
6 E9 ?0 B# h: U% B如果数组中不存在目标值 target，返回 [-1, -1]。
7 s1 k( B" L/ O% G+ U你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
1 X# T" B' q- D* H& h输入：nums = [5,7,7,8,8,10], target = 8
% ]+ n' W% `0 f! c输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
+ f7 O! Q  s7 k, \) N# P( P输出：[-1,-1]
示例 3：
+ F) H6 X  L6 W8 R4 Q输入：nums = [], target = 0
输出：[-1,-1]
: ]$ p9 |5 w' L1 [1
2
1 t# B: w* _5 L9 {3
4
5
6
5 k" i1 R  h( p9 _& w7
8
+ {( D0 ^$ s7 [  K+ q+ s# u4 I9
提示：

& d* V5 U, V; m  W0 <= nums.length <= 10(5)
-10(9) <= nums[i] <= 10(9)
9 o* A, i* j5 Z4 m" Lnums 是一个非递减数组
; a( c' t' [* p0 E; s$ p/ k7 n-10(9) <= target <= 10(9)
思路
关键步骤，与二分查找不同
. |0 M) }  {" C; I+ u1 \& h; D! v- qif(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
, G; f# Z6 T7 L* ^  L' T1 b9 Otarget==nums[mid]时，不结束循环，继续进入
两个if可以同时进入，寻找界限
设置限制，防止mid-1,mid+1越界
( c& ~1 v6 ]2 f# X3 r: Y1 v6 h, M代码
# D! j8 G6 m! bclass Solution {
- [1 d8 P  Y1 ^* u  W+ bpublic:
  z9 l9 K2 @3 X    int left=-1,right=-1;
, }2 e- n6 j, Y: n. k# t* N    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)  return vector<int>{-1,-1};
3 u8 w8 T6 q4 }  Y7 ~: C7 r        binary_search(nums,target,0,nums.size());
        return vector<int>{left,right};
    }
2 N5 F) n9 H- W$ ^' Y    void binary_search(vector<int>& nums,int target,int l ,int r){
        int mid=(r-l)/2+l;
        //printf("%d-%d\n",l,r);
: {. R- I6 o( F& a2 w9 n! m; G        if(target==nums[mid]){
2 X- O8 m) i& j! @0 e            if(left>mid||left<0)  left=mid;
            if(right<mid||right<0)   right=mid;
$ m/ M8 ^" ]% G: k' f- ~/ w6 ^        }
3 k+ o) K/ }7 Y, `        if(l>=r) return;
        if(target<=nums[mid]&&mid-1>=0)  binary_search(nums,target,l,mid-1);
0 [$ d7 Z. r- _# B        if(target>=nums[mid]&&mid+1<nums.size())   binary_search(nums,target,mid+1,r);
    }
+ u9 x0 {7 J0 K/ F) t5 Z; y};

; S5 j  D" [2 I$ u————————————————
$ r/ v, X& B; n; H- y$ J, T. F版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
9 Z& T' a6 p2 G8 g8 e0 [# Y4 j5 u/ x) _原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832

/ C) ~4 d0 Z0 c1 X( r2 H  W