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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
8 |, i& K; u% D' }* N3 P( G难度中等
9 y- {5 @5 w9 J5 ^给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
1 I: q# y# ]4 |. W如果数组中不存在目标值 target，返回 [-1, -1]。
" G* f$ h. Q) O+ y' `& _你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
* f. q+ H; E# R- I
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
* ^  `2 ^, z1 _5 a示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
9 T1 R9 [) p* R/ c6 w4 u; K8 x" j$ S1
2
7 D0 ]+ @5 r  V, E3 H7 ~/ @3
9 h! e) Y, n* A: k  m+ l- @5 ?4
3 F( f; @0 G2 n5
; p, l% X  G. L8 ]) P6
- I$ T% E4 d" g, h7
8
2 F% e2 h2 y; s$ [1 V$ `* z, F9
) c3 L5 A6 u5 }/ Q提示：
2 y( ~/ p$ Y, o0 Y( [! H
0 <= nums.length <= 10(5)
# u5 @$ t5 u1 ~9 \8 c" V-10(9) <= nums[i] <= 10(9)
nums 是一个非递减数组
-10(9) <= target <= 10(9)
, R7 P+ @/ D* d: C. j思路
关键步骤，与二分查找不同
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
# J6 B$ w  ~- z& Gtarget==nums[mid]时，不结束循环，继续进入
( o5 `6 ?" S% x7 Z+ H( T, Z两个if可以同时进入，寻找界限
' r3 Q' d0 R( v1 D! `5 @设置限制，防止mid-1,mid+1越界
/ }9 Y' B7 T/ [8 a3 w3 B代码
class Solution {
public:
$ V# p& c6 L- z3 w1 d2 s    int left=-1,right=-1;
& t, S( U  R- D5 v    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.size()==0)  return vector<int>{-1,-1};
        binary_search(nums,target,0,nums.size());
        return vector<int>{left,right};
( b0 ?) Z" f3 n; x  T& W0 s1 k    }
; _" `3 w0 L+ F    void binary_search(vector<int>& nums,int target,int l ,int r){
) R& v5 @$ U: w- M        int mid=(r-l)/2+l;
% N5 s  H. f0 u3 D8 J5 i, K        //printf("%d-%d\n",l,r);
        if(target==nums[mid]){
            if(left>mid||left<0)  left=mid;
            if(right<mid||right<0)   right=mid;
        }
        if(l>=r) return;
7 u- i9 t6 q  v3 ~. F  V$ E8 g        if(target<=nums[mid]&&mid-1>=0)  binary_search(nums,target,l,mid-1);
* I/ i) t6 T' s* z        if(target>=nums[mid]&&mid+1<nums.size())   binary_search(nums,target,mid+1,r);
$ n! l, s$ i$ l* ?1 ~    }
};

+ g! M' Z! D  P5 b. |————————————————
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 _, \+ @& j: f原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832


% o- A4 }1 G! ^& u4 D