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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
难度中等
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
" o& t+ p- n2 W如果数组中不存在目标值 target，返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
7 @6 C: Z' H- h( J. d3 [" j
+ h) P0 F- S. N# d. L1 V1 F示例 1：
. s7 @; V. ]& M/ Z输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
3 \/ n1 Y' \: k9 D3 {输入：nums = [5,7,7,8,8,10], target = 6
. f5 M2 M. T/ O4 e输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
. u" z! o0 ^* d( C* @( N* _输出：[-1,-1]
: y& V. x6 I3 @" h5 {, B% x; i3 r6 |1
1 ?! F' [* _# e0 p, f2
3
' h  Y) Y: G# ?! u4
5
1 {: K6 v. h0 D6
# a4 P2 w& ^# ?7
$ ]8 C7 R4 \" \; g- T- H) w8
& r/ L% M. ^+ ^+ t/ |% x9
提示：

2 ~; }6 w: q* _. `7 y( c) v) o) k. R0 <= nums.length <= 10(5)
-10(9) <= nums[i] <= 10(9)
# y. h' K$ X( O" Cnums 是一个非递减数组
-10(9) <= target <= 10(9)
' F+ m& X9 ?/ d3 E% X8 ?0 K思路
关键步骤，与二分查找不同
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
' [1 e" S8 ?6 _# \/ z4 atarget==nums[mid]时，不结束循环，继续进入
/ Z1 p+ K& o9 z# W" s* n! U% c- e两个if可以同时进入，寻找界限
/ m8 r+ `9 K0 c, x设置限制，防止mid-1,mid+1越界
! l6 E1 ]+ t' O/ e代码
class Solution {
public:
    int left=-1,right=-1;
    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};
    }
    void binary_search(vector<int>& nums,int target,int l ,int r){
  R  j7 ^/ R- w* F& D        int mid=(r-l)/2+l;
        //printf("%d-%d\n",l,r);
1 j% u# h+ q: v6 C- G        if(target==nums[mid]){
            if(left>mid||left<0)  left=mid;
            if(right<mid||right<0)   right=mid;
        }
) m# [0 J9 ~4 R) ]# q% A        if(l>=r) return;
        if(target<=nums[mid]&&mid-1>=0)  binary_search(nums,target,l,mid-1);
4 h% V- P4 {/ d. U- v6 A        if(target>=nums[mid]&&mid+1<nums.size())   binary_search(nums,target,mid+1,r);
) e0 K0 ~8 @  J( B: Z/ C& M    }
};

————————————————
+ {2 s2 u0 a2 u* V# I  ~( G; b& U) Y版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832

% C9 n# t3 S1 k
! T3 n6 I  T$ g% m; d