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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
难度中等
% ]% z! M" s2 J( Y: I' Y0 o给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
; i$ f+ [! |; A: \1 T5 P% k你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
9 \5 x! h$ T. o6 }
示例 1：
, _9 ]* d* X* u0 p$ ]% e# ~输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
  K$ A6 Z$ M9 r+ c5 U5 Y; b/ L示例 2：
6 r1 b* `, s2 m2 p+ B输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
; |" T& k. c/ r8 _8 L输出：[-1,-1]
9 K/ @5 w8 P% E! f+ f1
2 ?( M4 }7 C1 A1 U7 o9 K2
3
. @* A' w  h' h( |* G4
5
0 }& X& k, f5 `) e& n6
7
8
( t1 T/ @$ P% ^: H. q4 H  G8 }9
) H6 M8 y! a( S7 k提示：
. U9 `& p7 o7 d, V. e# K& W
0 <= nums.length <= 10(5)
! X! |; _. ^( I: l. a9 ]-10(9) <= nums[i] <= 10(9)
nums 是一个非递减数组
7 E6 G7 Q7 h" Y# K+ E# M- m-10(9) <= target <= 10(9)
& }  _8 r) e( B4 a思路
关键步骤，与二分查找不同
, I1 ~+ r1 C, d! t+ ^if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
target==nums[mid]时，不结束循环，继续进入
两个if可以同时进入，寻找界限
设置限制，防止mid-1,mid+1越界
代码
class Solution {
public:
    int left=-1,right=-1;
+ `! E5 {$ e  o0 F' s    vector<int> searchRange(vector<int>& nums, int target) {
( ]  e' t- N7 F# }0 m& E  f2 \. M        if(nums.size()==0)  return vector<int>{-1,-1};
5 y6 C% |6 H/ E5 u# c3 h        binary_search(nums,target,0,nums.size());
( L1 e2 G6 [9 l7 V4 [        return vector<int>{left,right};
    }
    void binary_search(vector<int>& nums,int target,int l ,int r){
        int mid=(r-l)/2+l;
        //printf("%d-%d\n",l,r);
( x0 P7 k4 {' B5 J+ k! W" _        if(target==nums[mid]){
; T$ c. u& }! x* v/ u: n- K            if(left>mid||left<0)  left=mid;
7 A0 ^; P% y: W2 ^* _* O/ |            if(right<mid||right<0)   right=mid;
        }
) W( R8 y6 I% G# x' @$ A! ?* m) ]6 b        if(l>=r) return;
        if(target<=nums[mid]&&mid-1>=0)  binary_search(nums,target,l,mid-1);
, c! C  j% t, S% O9 j0 t1 K, P% U        if(target>=nums[mid]&&mid+1<nums.size())   binary_search(nums,target,mid+1,r);
    }
! m2 G5 M, \; K/ s};
1 t2 ~) h. M% p' R9 W+ Z
————————————————
" L/ M$ ]# e7 p* y4 U  b版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
7 P' v! g! n2 D

7 X! H6 K! T7 k7 \9 W