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

约 5 分钟
文章信息 24 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 历史考题 100-200 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 京东 华为 拼多多 小米 虾皮 携程 LeetCode 热题 100 面试经典 150 题
标签
数组 二分查找 二分查找经典题
目录

题目描述

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

image-20230305132114938

题意分析

输入是一个非降序数组 nums 和一个目标值 target，要求返回长度为 2 的数组：target 第一次出现的下标和最后一次出现的下标。target 不在数组里时返回 [-1,-1]——注意这是一个必须显式处理的返回值，不是抛异常也不是返回空数组。

「数组已排序」这个条件透露的信息是：所有等于 target 的元素必然占据一段连续下标。所以答案一定形如闭区间 [l, r]，问题被化简成求这段区间的左右两个端点，而不是收集所有匹配下标。

题面还额外要求算法的时间复杂度为 $O(\log n)$。这条要求把线性扫描直接排除掉，也顺手排除了「先随便找到一个匹配位置，再向左右两侧逐格扩张」的折中做法——数组全等于 target 时扩张阶段就是一整遍遍历。

需要单独想清楚的边界情形有五类：数组为空；target 比所有元素都小或都大；整个数组都等于 target；target 只出现一次（此时首末下标相同）；数组只有一个元素。

解法：两次边界二分

核心思路

用 lowerBound(x) 找到第一个大于等于 x 的位置。第一次查 target 得到左端点，第二次查 target + 1 得到右端点后一位；若左端点越界或值不等于 target，说明目标不存在。

解题步骤

  • 二分查找第一个大于等于 target 的下标 left。
  • 若 left == n 或 nums[left] != target，返回 [-1, -1]。
  • 再查第一个大于等于 target + 1 的下标，减一得到右端点。
  • 二分始终使用左闭右开区间 [left, right)。

代码实现

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums, target);
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        return new int[]{left, lowerBound(nums, target + 1) - 1};
    }

    private int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

func searchRange(nums []int, target int) []int {
    left := lowerBound(nums, target)
    if left == len(nums) || nums[left] != target {
        return []int{-1, -1}
    }
    return []int{left, lowerBound(nums, target+1) - 1}
}

func lowerBound(nums []int, target int) int {
    left, right := 0, len(nums)

    for left < right {
        mid := left + (right-left)/2
        if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

复杂度分析

  • 时间复杂度：$O(log n)$，两次二分查找不改变量级。
  • 空间复杂度：$O(1)$。

关键点总结

  • lowerBound 返回第一个大于等于目标的位置，也可能返回 n。
  • nums[mid] == target 时仍收缩右边界，才能继续寻找最左位置。
  • 本题约束保证 target + 1 不溢出；它代表第一个严格大于 target 的边界。

易错点总结

  • 未校验左端点是否越界、是否等于目标，会把不存在的目标误判为存在。
  • 左闭右开区间应初始化 right = n，循环条件是 left < right。
  • 找右边界后忘记减一，会返回目标区间右侧的位置。
  • 将比较条件写成 nums[mid] <= target，会把 lowerBound 变成上边界查找。

相似题目

题目 难度 考察点
35. 搜索插入位置 简单 答案就是 lowerBound 本身，既不用求右端点也不用做存在性校验，适合单独练模板
278. 第一个错误的版本 简单 谓词由数组取值比较换成一次 API 调用，没有数组可看，最能暴露「二分找第一个为真」的本质
367. 有效的完全平方数 简单 在值域而不是下标上二分，判定式含乘法，要用 long 或除法改写以避免溢出
540. 有序数组中的单一元素 中等 谓词与 target 无关，要靠「配对下标的奇偶性是否被破坏」自己构造单调性
704. 二分查找 简单 元素互不相同，不存在重复段，只需返回任意匹配位置，是本题剥掉端点定位后的骨架
LCR 068. 搜索插入位置 简单 与 35 题同题换皮，可用来确认 lowerBound 能脱稿写对
LCR 070. 有序数组中的单一元素 中等 与 540 题同题换皮，重点是把奇偶配对的谓词再推一遍而不是背结论
剑指 Offer 53 - I. 在排序数组中查找数字 I 简单 只要出现次数，等于两个边界相减，连存在性校验都可以省掉（不存在时差值天然为 0）
剑指 Offer 53 - II. 0～n-1中缺失的数字 简单 谓词是 nums[i] != i，二分的对象从「值的位置」变成「下标与值是否错位」
面试题 10.05. 稀疏数组搜索 简单 数组里夹着空串，mid 落在空串上时必须先线性挪动，最坏情况不再是严格的 $O(\log n)$