LeetCode【0034】在排序数组中查找元素的第一个和最后一个位置

1 中文题目

给定一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

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

示例：

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

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

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

提示：

• $0\le nums.length\le 10^5$
• $-10^9\le nums[i]\le 10^9$
• nums 是一个非递减数组
• $-10^9\le target\le 10^9$

---

2 求解方法：左右边界二分查找

2.1 方法思路

方法核心

• 使用两次改进的二分查找
• 分别查找目标值的左右边界
• 通过不同的条件控制边界的移动

实现步骤

（1）查找左边界的过程：

• 初始化左右指针，分别指向数组的开始和结束
• 在循环中计算中间位置
• 当找到大于或等于目标值的元素时，记录该位置并继续往左找
• 当找到小于目标值的元素时，需要往右找
• 最终找到第一个等于目标值的位置
• 需要判断是否越界以及是否真的找到了目标值

（2）查找右边界的过程：

• 同样初始化左右指针
• 在循环中不断更新中间位置
• 当找到小于或等于目标值的元素时，继续往右找
• 当找到大于目标值的元素时，需要往左找
• 最终找到最后一个等于目标值的位置
• 同样需要进行边界检查

方法示例

输入：nums = [5,7,7,8,8,10], target = 8

左边界查找过程：
1. 初始状态：
   left = 0, right = 5
   mid = 2, nums[mid] = 7 < target
   left = mid + 1 = 3

2. 第二次迭代：
   left = 3, right = 5
   mid = 4, nums[mid] = 8 == target
   right = mid - 1 = 3

3. 第三次迭代：
   left = 3, right = 3
   mid = 3, nums[mid] = 8 == target
   right = mid - 1 = 2

4. 循环结束：
   left = 3，找到左边界

右边界查找过程：
1. 初始状态：
   left = 0, right = 5
   mid = 2, nums[mid] = 7 < target
   left = mid + 1 = 3

2. 第二次迭代：
   left = 3, right = 5
   mid = 4, nums[mid] = 8 == target
   left = mid + 1 = 5

3. 第三次迭代：
   left = 5, right = 5
   mid = 5, nums[mid] = 10 > target
   right = mid - 1 = 4

4. 循环结束：
   right = 4，找到右边界

返回：[3, 4]

2.2 Python代码

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binary_search_left(nums, target):
            # 寻找左边界的二分查找
            left, right = 0, len(nums) - 1
            
            while left <= right:
                mid = left + (right - left) // 2
                # 如果中间值大于或等于目标值，继续往左找
                if nums[mid] >= target:
                    right = mid - 1
                # 如果中间值小于目标值，往右找
                else:
                    left = mid + 1
                    
            # 判断是否找到目标值
            if left >= len(nums) or nums[left] != target:
                return -1
            return left
            
        def binary_search_right(nums, target):
            # 寻找右边界的二分查找
            left, right = 0, len(nums) - 1
            
            while left <= right:
                mid = left + (right - left) // 2
                # 如果中间值小于或等于目标值，继续往右找
                if nums[mid] <= target:
                    left = mid + 1
                # 如果中间值大于目标值，往左找
                else:
                    right = mid - 1
                    
            # 判断是否找到目标值
            if right < 0 or nums[right] != target:
                return -1
            return right
            
        # 特殊情况处理
        if not nums:
            return [-1, -1]
            
        # 分别查找左右边界
        left_bound = binary_search_left(nums, target)
        right_bound = binary_search_right(nums, target)
        
        return [left_bound, right_bound]

2.3 复杂度分析

• 时间复杂度：O(log n)
  • 两次二分查找
  • 每次二分查找的时间复杂度为O(log n)
• 空间复杂度：O(1)
  • 只使用常数额外空间
  • 不随输入规模增长

---

3 题目总结

题目难度：中等
数据结构：数组
应用算法：左右边界二次二分查找

原文地址：https://blog.csdn.net/qq_32882309/article/details/143739911

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！