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

Categories:

Tags:

题目描述
思路分析
1. 解法一：两次二分（记录结果法）（推荐）
2. 解法二：两次二分（偏移法）
相似题目

题目描述

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

思路分析

解法一：两次二分（记录结果法）（推荐）

核心思路：

在有重复元素的有序数组中查找目标范围，需要两次独立的二分查找，分别锁定左边界和右边界。

找左边界：当 nums[mid] == target 时，不立即返回，而是记录 res = mid 并继续向左收缩（right = mid - 1），直到找到最左边等于 target 的位置。

找右边界：当 nums[mid] == target 时，记录 res = mid 并继续向右扩展（left = mid + 1），找到最右边等于 target 的位置。

两次二分互相独立，每次都从头开始扫描，最终组合成 [left, right] 结果返回。

复杂度分析：

时间复杂度：O(log n)，其中 n 为数组长度，两次独立的二分查找各 O(log n)

空间复杂度：O(1)，只使用了常数级别的额外空间

class Solution {

    public int[] searchRange(int[] nums, int target) {
        return new int[]{findFirst(nums, target), findLast(nums, target)};
    }

    // 查找第一个等于 target 的位置（左边界）
    private int findFirst(int[] nums, int target) {
        int left = 0, right = nums.length - 1, res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                // 命中时记录结果，并继续向左收缩
                res = mid;
                right = mid - 1;
            }
        }
        return res;
    }

    // 查找最后一个等于 target 的位置（右边界）
    private int findLast(int[] nums, int target) {
        int left = 0, right = nums.length - 1, res = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else {
                // 命中时记录结果，并继续向右扩展
                res = mid;
                left = mid + 1;
            }
        }
        return res;
    }
}

func searchRange(nums []int, target int) []int {
    // 查找第一个等于 target 的位置（左边界）
    findFirst := func() int {
        left, right, res := 0, len(nums)-1, -1
        for left <= right {
            mid := left + (right-left)/2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            } else {
                // 命中时记录结果，并继续向左收缩
                res = mid
                right = mid - 1
            }
        }
        return res
    }

    // 查找最后一个等于 target 的位置（右边界）
    findLast := func() int {
        left, right, res := 0, len(nums)-1, -1
        for left <= right {
            mid := left + (right-left)/2
            if nums[mid] < target {
                left = mid + 1
            } else if nums[mid] > target {
                right = mid - 1
            } else {
                // 命中时记录结果，并继续向右扩展
                res = mid
                left = mid + 1
            }
        }
        return res
    }

    return []int{findFirst(), findLast()}
}

解法二：两次二分（偏移法）

核心思路：

将”找左边界”转化为：找第一个 ≥ target 的位置（lower bound）；将”找右边界”转化为：找第一个 > target 的位置再 -1（upper bound - 1）。

这样两次二分使用统一的 lower_bound 逻辑，写法更简洁，只需传入不同的比较值。

左边界 = lowerBound(target)，右边界 = lowerBound(target + 1) - 1；最后校验左边界是否有效且等于 target。

复杂度分析：

时间复杂度：O(log n)，其中 n 为数组长度，两次调用 lower_bound 各 O(log n)

空间复杂度：O(1)，只使用了常数级别的额外空间

class Solution {

    public int[] searchRange(int[] nums, int target) {
        int left = lowerBound(nums, target);
        // 若左边界越界或不等于 target，说明不存在
        if (left == nums.length || nums[left] != target) {
            return new int[]{-1, -1};
        }
        // 右边界 = 第一个 > target 的位置 - 1
        int right = lowerBound(nums, target + 1) - 1;
        return new int[]{left, right};
    }

    // 找第一个 >= target 的下标（lower bound）
    private int lowerBound(int[] nums, int target) {
        int left = 0, 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 {
    // 找第一个 >= target 的下标（lower bound）
    lowerBound := func(t int) int {
        left, right := 0, len(nums)
        for left < right {
            mid := left + (right-left)/2
            if nums[mid] < t {
                left = mid + 1
            } else {
                right = mid
            }
        }
        return left
    }

    left := lowerBound(target)
    // 若左边界越界或不等于 target，说明不存在
    if left == len(nums) || nums[left] != target {
        return []int{-1, -1}
    }
    // 右边界 = 第一个 > target 的位置 - 1
    right := lowerBound(target+1) - 1
    return []int{left, right}
}

相似题目

题目	难度	考察点
33. 搜索旋转排序数组	中等	旋转数组中的二分
35. 搜索插入位置	简单	二分找插入位置（lower bound）
278. 第一个错误的版本	简单	二分找左边界
744. 寻找比目标字母大的最小字母	简单	二分右边界变体
153. 寻找旋转排序数组中的最小值	中等	二分边界条件判断
702. 搜索长度未知的有序数组	中等	未知长度有序数组二分
2529. 正整数和负整数的最大计数	简单	lower bound / upper bound 综合应用

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/81925119