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

一、题目描述：

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

1. 示例 1：

   • 输入：nums = [5,7,7,8,8,10], target = 8
   • 输出：[3,4]

2. 示例 2：

   • 输入：nums = [5,7,7,8,8,10], target = 6
   • 输出：[-1,-1]

3. 示例 3：

   • 输入：nums = [], target = 0
   • 输出：[-1,-1]

• 提示：
  • 0 ≤ n u m s . l e n g t h ≤ 1 0 5 0 \\leq nums.length \\leq 10^5 0≤nums.length≤105
  • − 1 0 9 ≤ n u m s [ i ] ≤ 1 0 9 -10^9 \\leq nums[i] \\leq 10^9 −109≤nums[i]≤109
  • − 1 0 9 ≤ t a r g e t ≤ 1 0 9 -10^9 \\leq target \\leq 10^9 −109≤target≤109
  • nums 是一个非递减数组

二、解决思路和代码

1. 解决思路

• 分析：根据题目，nums 是一个非递减数组，可以通过递归方式的二分查找解决。解决方法：定义 res = [-1, -1]， res[0]是目标元素出现的第一个位置， res[1] 是目标元素出现的最后一个位置。思路如下：
  • 首先，使用二分查找的方法找到第一个 nums[mid]=target 的位置
  • 然后，对 nums[:mid] 和 nums[mid+1:] 进行二分查找，在左边找到第一个开始的位置，以及右边结束的位置。常规的二分查找是在已排序数组中找到目标及返回，那么这道题目中，怎样的条件能在左边找到目标元素的起始和结束位置呢？
    • 在左边找元素的起始位置。当每次找到 nums[mid]=target 时，res[0]=-1【第一次找到目标元素】或者 res[0]=mid_pre ，mid_pre为上一次找到目标元素的位置。
      • 当 $mid-1>=0andnums[mid-1]==target$，起始位置还在 mid 的左边，继续进行递归查找
      • 否则，当前找到的 mid 就是起始位置，修改 res[0]=mid
    • 同理，在右边找元素的结束位置。当每次找到 nums[mid]=target 时，res[1]=-1【第一次找到目标元素】或者 res[1]=mid_pre ，mid_pre为上一次找到目标元素的位置。
      • 当 $mid+1<len(nums)andnums[mid+1]==target$，结束位置还在 mid 的右边，继续进行递归查找
      • 否则，当前找到的 mid 就是结束位置，修改 res[1]=mid
  • 举例：
    

2. 代码

from typing import *
class Solution:def binarySearch(self, nums: List[int], target: int, left: int, right:int, res: List[int]):if left>right: returnwhile left<=right:mid = (left+right)//2if nums[mid]<target: left = mid+1elif nums[mid]>target:right = mid-1else:if res[0]==-1 or mid<res[0]:if mid-1>=0 and nums[mid-1]==target:  ## leftself.binarySearch(nums, target, left, mid-1, res)else:res[0] = midif res[1]==-1 or mid>res[1]:if mid+1<len(nums) and nums[mid+1]==target:  ## rightself.binarySearch(nums, target, mid+1, right, res)else:res[1] = midbreakreturndef searchRange(self, nums: List[int], target: int) -> List[int]:if len(nums)==0:return [-1,-1]if len(nums)==1:return [0,0] if nums[0]==target else [-1,-1]res = [-1, -1]self.binarySearch(nums, target, 0, len(nums)-1, res)return res if res[0]!=-1 and res[1]!=-1 else [-1,-1]