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

杨利霞

34. 在排序数组中查找元素的第一个和最后一个位置
0 J3 C1 x7 n) {3 B6 `5 E难度中等
% z7 X) R: J' C% p3 p! i' @. _给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
0 K4 Z' G; n' r如果数组中不存在目标值 target，返回 [-1, -1]。
' l% f6 c2 x+ d3 R! e- N+ e9 T. B你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
! [' h6 q2 D  t' X' e# I- @  I1
8 z8 W  H- L' @0 Z- }2
3
4
" h! s) Z- Z  c5 @! a5
, K  W* B# H8 B+ t; T7 T9 i6
% v, v% J# s9 y$ C9 x  I7
8
" l5 t% ?$ G& R; n- D3 f/ M9
( j$ x) _3 J* R提示：

$ Z- M5 j7 A' H8 ?, Y( ]0 <= nums.length <= 10(5)
5 g! m8 L7 n' x9 g0 H% M-10(9) <= nums[i] <= 10(9)
nums 是一个非递减数组
; T: H0 H8 e. m1 U5 F6 L( V( k5 {-10(9) <= target <= 10(9)
+ U  A; P! o; X- C" |; x9 i: q$ d思路
1 Z- v; l# A/ o2 g0 s5 k关键步骤，与二分查找不同
if(target**<=**nums[mid]&&mid-1>=0) binary_search(nums,target,l,mid-1);
target==nums[mid]时，不结束循环，继续进入
两个if可以同时进入，寻找界限
& p9 [, v0 j; z6 Q4 C- W5 P设置限制，防止mid-1,mid+1越界
# M+ y$ |! u; b代码
1 }5 A  A7 w/ e: R. v( g( bclass Solution {
/ n7 k: \' e4 ]3 ypublic:
' R5 g# N7 l4 ]: F9 e) D0 u5 J/ e    int left=-1,right=-1;
    vector<int> searchRange(vector<int>& nums, int target) {
7 Q( S, i" a5 \& M" C# z) \        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){
        int mid=(r-l)/2+l;
        //printf("%d-%d\n",l,r);
        if(target==nums[mid]){
            if(left>mid||left<0)  left=mid;
3 V/ b$ t, Z2 _5 i4 S1 [' L            if(right<mid||right<0)   right=mid;
. Z) {& E# C- {: h9 @  H        }
        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);
2 ^8 |0 u/ n3 M$ k& O7 v    }
};

————————————————
版权声明：本文为CSDN博主「嗝~~~~」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
. r( X5 k/ C  z9 y6 W原文链接：https://blog.csdn.net/qq_41735944/article/details/126648832
, a& G. \! W* S: D# m5 g0 j
/ Z* d/ l5 y6 y- o7 W" E% D
5 I5 V5 B6 l; _( ?; v, n