LeetCode中怎么在排序数组中查找数字

# LeetCode中怎么在排序数组中查找数字

## 引言

在LeetCode的算法题库中，"在排序数组中查找数字"是一个经典的二分查找问题（如题目34. Find First and Last Position of Element in Sorted Array）。这类问题考察对二分查找算法的灵活运用，需要处理目标数字的首次和末次出现位置。本文将详细解析解题思路，并提供Python代码实现。

---

## 问题描述

给定一个按照升序排列的整数数组 `nums` 和一个目标值 `target`，要求：
1. 找出 `target` 在数组中的开始位置和结束位置
2. 如果不存在则返回 `[-1, -1]`
3. 时间复杂度必须为 **O(log n)**

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

解题思路

二分查找变体

常规二分查找找到目标值后立即返回，但本题需要找到边界。我们需要两次二分查找： 1. 查找左边界：找到第一个等于 target 的位置 2. 查找右边界：找到最后一个等于 target 的位置

左边界查找关键点：

• 当 nums[mid] >= target 时收缩右边界
• 最终检查 left 是否越界或值不匹配

右边界查找关键点：

• 当 nums[mid] <= target 时收缩左边界
• 最终检查 right 是否越界或值不匹配

代码实现

def searchRange(nums, target):
    def find_left():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] >= target:
                right = mid - 1
            else:
                left = mid + 1
        return left if left < len(nums) and nums[left] == target else -1
    
    def find_right():
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right if right >= 0 and nums[right] == target else -1
    
    left_pos = find_left()
    right_pos = find_right()
    return [left_pos, right_pos] if left_pos != -1 and right_pos != -1 else [-1, -1]

复杂度分析

• 时间复杂度：O(log n)
  两次二分查找各自消耗 O(log n) 时间
• 空间复杂度：O(1)
  仅使用常数级额外空间

边界情况处理

1. 空数组：直接返回 [-1, -1]
2. 目标值不存在：检查最终左右指针的值是否有效
3. 单一元素数组：同时作为左右边界处理

变式问题

统计数字出现次数

找到左右边界后，出现次数即为 right_pos - left_pos + 1

查找插入位置（LeetCode 35）

调整二分查找条件即可解决：

def searchInsert(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    return left

总结

1. 排序数组中的查找问题优先考虑二分法
2. 通过修改二分法的收缩条件来处理边界查找
3. 注意检查最终指针的有效性
4. 该模板可扩展到其他类似问题（如求平方根）

掌握这类问题的核心在于理解二分查找的区间收缩逻辑，并通过练习培养对边界条件的敏感度。建议在LeetCode上尝试相关练习题（如34、35、704题）来巩固理解。 “`

文章通过问题分析、代码实现、边界处理等模块完整解析了该题型，符合技术文章的结构要求，字数约850字。可根据需要调整代码示例的语言或补充更多变式问题。