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

专题归类： 09-二分查找 LeetCode 链接： https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

---

在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode

题目描述

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

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

你必须设计并实现时间复杂度为 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]

提示：

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

---

题目详细分析

数据范围含义：

• nums.length <= 10^5：O(log n) 约 17 次比较即可完成。
• 元素范围 ±10^9：不会溢出（mid 用 left + (right-left)//2 安全）。
• 非递减（可能有重复元素）：非递减 = 升序 + 允许重复。重复元素的存在使得需要找”范围”而非单个位置。

问题本质：

• 找左边界：第一个 >= target 的位置（也称为 lower_bound）。
• 找右边界：最后一个 <= target 的位置（也称为 upper_bound - 1）。
• 如果左边界有效（不越界且值等于 target），则返回 [左, 右]；否则返回 [-1, -1]。

边界条件：

• 空数组 → 直接返回 [-1, -1]。
• target 不存在 → 左边界处值不等于 target，返回 [-1, -1]。
• target 小于所有元素 → 左边界为 0，越界/不等于，返回 [-1, -1]。
• target 大于所有元素 → 左边界为 len(nums)，越界，返回 [-1, -1]。

---

小白版直白理解

就像在成绩单上找所有考了 90 分的同学——成绩单是按分数从低到高排好的。你要找出第一个考 90 分的同学（左边界）和最后一个考 90 分的同学（右边界）。

如果根本没人考 90 分，就报告没找到。

比如说成绩单是 [75, 82, 90, 90, 90, 95]：

• 第一个 90 在位置 2。
• 最后一个 90 在位置 4。
• 所以返回 [2, 4]。

---

解题思路

思路一：左右边界分开查找（推荐）

核心思想： 分别用两个二分查找函数找左边界和右边界。

• 左边界（lower_bound）：找第一个 >= target 的位置。nums[mid] < target 时排除左半，否则排除右半。
• 右边界（upper_bound）：找最后一个 <= target 的位置。nums[mid] <= target 时排除左半，否则排除右半。
• 或者找第一个 > target 的位置，然后减 1 得到右边界。

搜索过程可视化（以 nums=[5,7,7,8,8,10], target=8 为例）：

找左边界（第一个 >= 8）：
  [5, 7, 7, 8, 8, 10]  l=0, r=5, mid=2, nums[2]=7<8 → l=3
  [8, 8, 10]            l=3, r=5, mid=4, nums[4]=8>=8 → r=3
  [8]                   l=3, r=3, mid=3, nums[3]=8>=8 → r=2
  l=3 > r=2, 返回 l=3

找右边界（第一个 > 8 的位置 - 1）：
  找第一个 > 8 的位置，得到下标 5，减 1 得 4
  或直接用右边界模板得到 4

def searchRange(nums, target):
    def lower_bound():
        """找第一个 >= target 的位置"""
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] < target:
                l = mid + 1  # mid 太小，排除左半
            else:
                r = mid - 1  # mid >= target，收缩右边界
        return l  # l 即第一个 >= target 的位置
 
    def upper_bound():
        """找最后一个 <= target 的位置"""
        l, r = 0, len(nums) - 1
        while l <= r:
            mid = l + (r - l) // 2
            if nums[mid] <= target:
                l = mid + 1  # mid <= target，收缩左边界
            else:
                r = mid - 1  # mid 太大，排除右半
        return r  # r 即最后一个 <= target 的位置
 
    left = lower_bound()
    # 验证左边界是否有效
    if left >= len(nums) or nums[left] != target:
        return [-1, -1]
 
    right = upper_bound()
    return [left, right]

思路二：利用 Python 内置 bisect 库

核心思想： Python 的 bisect_left 和 bisect_right 正是本题需要的二分查找工具。

import bisect
 
def searchRange(nums, target):
    left = bisect.bisect_left(nums, target)
    if left == len(nums) or nums[left] != target:
        return [-1, -1]
    right = bisect.bisect_right(nums, target) - 1
    return [left, right]

注意： 面试时不能直接调库，但在实际工程中可以这样写。理解 bisect_left / bisect_right 的内部实现是更重要的。

时间复杂度： O(log n)，两次二分各 O(log n)。 空间复杂度： O(1)。

---

易错点

1. 左边界模板的 if 条件区别：
   • 左边界：nums[mid] < target → l = mid + 1
   • 右边界：nums[mid] <= target → l = mid + 1
   • 仅仅是一个等号的差别！等号在哪边决定了是找左边界还是右边界。
2. 验证逻辑：必须检查 left >= len(nums)（越界）或 nums[left] != target（值不存在），二者任一成立则返回 [-1, -1]。
3. 空数组：len(nums) == 0 时 lower_bound() 返回 0，检查 left >= len(nums) 时触发，返回 [-1, -1]。
4. 右边界用 left_bound 加等号的技巧：如果记不住右边界模板，可以用”找第一个 > target 的位置，减 1 得右边界”代替。即 bisect_right(nums, target) - 1。
5. 死循环：在 while l <= r 的写法中，每次更新为 mid +/- 1，不会死循环。但如果用 while l < r 需要特别注意 mid 的取值方式。

---

框架提炼

二分查找的三种模板：

# 1. 标准二分（精确查找）
def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            l = mid + 1
        else:
            r = mid - 1
    return -1
 
# 2. 左边界（第一个 >= target）
def lower_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] < target:  # 注意：没有等号
            l = mid + 1
        else:
            r = mid - 1
    return l
 
# 3. 右边界（最后一个 <= target）
def upper_bound(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = l + (r - l) // 2
        if nums[mid] <= target:  # 注意：有等号
            l = mid + 1
        else:
            r = mid - 1
    return r

记忆技巧：

• lower_bound vs upper_bound 就差一个等号。
• 等号在左（nums[mid] <= target）→ 右边界（向左收缩）。
• 等号在右（nums[mid] < target）→ 左边界（向右收缩）。
• 最终 lower_bound 返回 l，upper_bound 返回 r。

---

关联题目

• 35-搜索插入位置 — 本题的左边界查找就是 35 题的完整解法，强烈建议对比学习。
• 33-搜索旋转排序数组 — 二分查找的变体，在旋转数组中搜索 target，二分思想的核心不变。
• 704-二分查找 — 最基础的标准二分，掌握模板后再学边界二分会更容易。
• 69-x的平方根 — 应用左边界二分思想的另一个例子，在整数范围内找平方根的整数部分。