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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
+ m3 }& m, i/ w# X难度中等
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
' C3 A/ o4 P0 L# C5 U1 g9 x如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

5 h! C/ W6 q. Z3 @+ l示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
& F- z$ w* |; {# D$ f输出：[3,4]
示例 2：
) w6 L' _; V% _& W" n0 N输入：nums = [5,7,7,8,8,10], target = 6
; j% y5 [+ E4 q" n; n/ Y! n输出：[-1,-1]
8 ?1 }8 c: N, L示例 3：
% ]8 }; |- W( u5 j* s) m) a输入：nums = [], target = 0
/ \' c, N, |" c0 i7 f0 \2 M, c/ A输出：[-1,-1]
7 A, {6 F" [/ L, z: Z. z9 q- O" s7 l1
2
  O) {9 Q3 ^) N- c! D( \3
4
8 w7 W/ |  r+ e" ]5
; `" b8 |1 k3 T5 G% ]6
7
5 w8 Z  y! N! z2 c1 z$ C8
9
8 u! E8 B  h/ O& @! |) C' Y7 t提示：

( ~7 J  M" P  Z6 V0 <= nums.length <= 10(5)
-10(9) <= nums[i] <= 10(9)
nums 是一个非递减数组
' F1 R& E/ Q5 r) ^4 y-10(9) <= target <= 10(9)
思路
关键步骤，与二分查找不同
8 k# D1 g, Y% Fif(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
: C, V" K3 ?% }' c+ \  y. utarget==nums[mid]时，不结束循环，继续进入
- i4 P3 t, n9 L( h! f, ~% o两个if可以同时进入，寻找界限
设置限制，防止mid-1,mid+1越界
" B1 @+ j2 h; ], Y8 M' {代码
class Solution {
5 L/ m, Y* w$ Ipublic:
2 q) Q$ z3 Q% g( _& l( s+ F! a$ _    int left=-1,right=-1;
    vector<int> searchRange(vector<int>& nums, int target) {
' f5 g8 G/ H4 j0 V; R# ]0 Z, Z        if(nums.size()==0)  return vector<int>{-1,-1};
        binary_search(nums,target,0,nums.size());
        return vector<int>{left,right};
    }
# [) C+ [$ N5 c9 r1 D+ T    void binary_search(vector<int>& nums,int target,int l ,int r){
        int mid=(r-l)/2+l;
        //printf("%d-%d\n",l,r);
  }  O2 N' y7 G( E        if(target==nums[mid]){
3 X+ l7 S) e/ p4 K            if(left>mid||left<0)  left=mid;
- K  c8 ~) L! s3 \; X: u! J% O            if(right<mid||right<0)   right=mid;
+ q  o# f2 @, \* `8 T        }
6 j4 q5 {9 ^- V' ^0 u9 p8 e        if(l>=r) return;
+ F1 z5 X- E+ d  f0 g        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);
    }
};

————————————————
0 V1 L& }9 E0 v; e  C, c5 `版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
/ b. P9 c. m2 P' ]+ b# M1 ~4 X