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

今天我要和大家分享一道非常经典的二分查找题目 - LeetCode 34「在排序数组中查找元素的第一个和最后一个位置」。这道题看似简单，实则暗藏玄机，是理解二分查找边界处理的绝佳材料。

📚 从生活场景说起#

想象你在整理一叠按时间顺序排好的照片，其中有多张是同一天拍的。如果要找出某一天最早和最晚拍的那张照片，你会怎么做？高效的方法是先用二分找到这一天的任意一张照片，然后再分别向左右寻找边界。这正是我们今天要解决的问题的生活映射！

问题描述#

题目目标#

给定一个按照非递减顺序排列的整数数组 nums 和一个目标值 target ，找出 target 在数组中的起始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。题目要求算法时间复杂度为 O(log n)。

示例 1#

输入： nums = [5,7,7,8,8,10], target = 8 输出： [3,4] 说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。

💡 问题解析#

题目要求：给定一个按升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值，返回 [-1, -1]。

示例：

// 示例1：目标值存在且连续出现
// 输入：nums = [5,7,7,8,8,10], target = 8
// 输出：[3,4]（8 出现在下标 3 到 4）

// 示例2：目标值不存在
// 输入：nums = [5,7,7,8,8,10], target = 6
// 输出：[-1,-1]（数组中没有 6）

java

🤔 思路发展历程#

让我们看看解决这个问题时，思维是如何层层递进的：

1. 朴素思路#

最直观的方法是遍历一遍数组，记录第一次和最后一次出现的位置。但这种方法的时间复杂度是O(n)，没有利用数组已排序的特性。

2. 二分查找思路#

既然数组已排序，我们可以用二分查找将时间复杂度优化到O(log n)。关键在于设计两个二分查找：一个找左边界，一个找右边界。

🚀 优雅的解决方案#

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 特判：空数组的情况
        if (nums == null || nums.length == 0) {
            return new int[]{-1, -1};
        }

        // 分别查找左右边界
        int leftBorder = findBorder(nums, target, true); // 查找 target 第一次出现的位置
        int rightBorder = findBorder(nums, target, false); // 查找 target 最后一次出现的位置

        // 按题目要求返回 [起始下标, 结束下标]
        return new int[]{leftBorder, rightBorder};
    }

    // 查找边界的统一函数，isLeft为true时查找左边界，false时查找右边界
    private int findBorder(int[] nums, int target, boolean isLeft) {
        int left = 0; // 二分左边界（包含）
        int right = nums.length - 1; // 二分右边界（包含）

        // 在闭区间 [left, right] 内搜索目标边界
        while (left <= right) {
            int mid = left + (right - left) / 2; // 中点下标，防溢出写法

            // 命中 target 后，不立刻返回，继续向对应方向逼近边界
            if (nums[mid] == target) {
                if (isLeft) {
                    // 查找左边界：若 mid 已是最左 target，直接返回
                    if (mid == 0 || nums[mid - 1] != target) {
                        return mid;
                    }
                    // 否则左边还存在 target，继续向左收缩
                    right = mid - 1;
                } else {
                    // 查找右边界：若 mid 已是最右 target，直接返回
                    if (mid == nums.length - 1 || nums[mid + 1] != target) {
                        return mid;
                    }
                    // 否则右边还存在 target，继续向右收缩
                    left = mid + 1;
                }
            } else if (nums[mid] < target) {
                // 中间值偏小，目标只能在右半区
                left = mid + 1;
            } else {
                // 中间值偏大，目标只能在左半区
                right = mid - 1;
            }
        }

        // 没有找到目标边界（即数组中不存在 target）
        return -1;
    }
}

java

📝 代码详解#

让我们深入理解这个优雅的解决方案：

1. 整体架构#

我们设计了一个统一的边界查找函数，通过布尔参数控制是查找左边界还是右边界。这种设计既减少了代码重复，又让逻辑更加清晰。

2. 边界查找的精妙之处#

当找到目标值时，我们并不立即返回，而是：

查找左边界时，我们要确认前一个数不是目标值
查找右边界时，我们要确认后一个数不是目标值这样就能精确定位边界位置。

3. 条件判断的艺术#

代码中的边界检查（mid == 0 或 mid == nums.length - 1）确保了我们不会发生数组越界。这些细节体现了代码的健壮性。

🎯 易错点剖析#

返回值处理
- 必须先判断数组为空的情况
- 当目标值不存在时，要返回[-1, -1]
边界条件
- 别忘了检查数组首尾的特殊情况
- 当找到目标值时，不要急于返回
循环终止条件
- while循环的条件是 left <= right
- 这确保了不会漏掉单个元素的情况

💡 举一反三#

这道题的思路可以延伸到很多场景：

查找最后一个小于目标值的位置
- 只需稍微修改边界判断条件
查找第一个大于目标值的位置
- 类似的二分思路，不同的判断条件
统计目标值的出现次数
- 可以用右边界减去左边界再加1

🌟 面试技巧#

展示思维过程
- 先说明暴力解法，再优化到二分
- 体现你的算法思维能力
代码优化意识
- 展示代码复用和模块化的能力
- 注意代码的可读性和维护性
考虑周全
- 主动提及边界情况的处理
- 展示你考虑问题的全面性