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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
难度中等
- a8 W4 y6 s- e给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
; b; P% K0 Y0 B9 s- S8 Y) Z; z如果数组中不存在目标值 target，返回 [-1, -1]。
) V3 ~- x4 A/ \, D2 V你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

/ q: `9 b$ Y  L+ V+ X3 K示例 1：
* G+ V" Y. a- Q/ R& J; Q$ V5 F输入：nums = [5,7,7,8,8,10], target = 8
5 I' m6 n+ b0 V% F0 l输出：[3,4]
示例 2：
: u  ]- M1 u3 \" T输入：nums = [5,7,7,8,8,10], target = 6
) {5 ]; Y0 d0 A5 R输出：[-1,-1]
4 c4 a. @$ `$ |* E% n1 [示例 3：
4 h' H' t9 e7 A9 S3 ^5 i! C输入：nums = [], target = 0
输出：[-1,-1]
1
8 a( |" O, c& {2 r% f$ l  b8 }2
# |9 ~' X: u) x7 D7 C! X/ t3
4
; I0 H! [5 g3 C) {5
6
0 Y+ K2 K2 V  u5 E: L0 J7
8
. J6 v, ]5 `- X, Z$ ^5 ~9
! y7 O& Z# p! t6 @" `5 X提示：

3 u! _4 P# j4 G. H; s( M0 <= nums.length <= 10(5)
-10(9) <= nums[i] <= 10(9)
; T8 L5 t6 e* A1 E' |4 N/ u: knums 是一个非递减数组
-10(9) <= target <= 10(9)
! y1 H" n7 [" n1 d( n思路
! n4 x( a8 n4 ?) u0 X( B6 m关键步骤，与二分查找不同
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
) {' F: Y/ ^* t4 V/ C  \target==nums[mid]时，不结束循环，继续进入
两个if可以同时进入，寻找界限
* |6 i# E( n8 M) X& u0 g设置限制，防止mid-1,mid+1越界
代码
class Solution {
public:
& ?9 n& p1 }8 z, x; x' x& Y2 o: C    int left=-1,right=-1;
    vector<int> searchRange(vector<int>& nums, int target) {
" H4 B( O, d; F* @7 E" P        if(nums.size()==0)  return vector<int>{-1,-1};
        binary_search(nums,target,0,nums.size());
8 s8 k; N9 M! R& }3 Z& h; f        return vector<int>{left,right};
8 U, n2 p! u' x* `1 o: J7 o    }
, ]: S- t/ K' A# L: O    void binary_search(vector<int>& nums,int target,int l ,int r){
        int mid=(r-l)/2+l;
, X) A1 m7 y4 X  s        //printf("%d-%d\n",l,r);
        if(target==nums[mid]){
            if(left>mid||left<0)  left=mid;
+ y1 X/ V2 t8 ~) c6 }            if(right<mid||right<0)   right=mid;
0 Q6 e8 U" T& Y! m        }
( n0 K! r+ }8 [' ]        if(l>=r) return;
        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);
9 F: V$ [$ h& A- D! p0 J7 x* k    }
0 }+ z+ K* @  q1 b' e# Y};
$ Q+ Z) W7 U6 z+ u# l3 ?3 @
————————————————
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832

  d7 u. V1 d% `0 C