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

一、题目

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

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

二、题解

思路：两次二分查找

既然要找起始和结束位置，最清晰的思路就是进行两次二分查找：

  1. 第一次：寻找左边界（第一个出现的位置）。
  2. 第二次：寻找右边界（最后一个出现的位置）。

核心的修改在于，当我们在二分查找中遇到 nums[mid] == target 时，不要立即返回。

  • 找左边界时： 既然我们找到了一个目标值，说明“第一个”目标值要么是当前的 mid，要么在 mid 的左侧。所以我们要记录下当前的 mid，然后收缩右边界（right = mid - 1），继续向左半部分搜索。
  • 找右边界时： 同理，说明“最后一个”目标值要么是当前的 mid，要么在 mid 的右侧。所以我们记录下当前的 mid，然后收缩左边界（left = mid + 1），继续向右半部分搜索。
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        // 边界情况处理
        if (nums == null || nums.length == 0) {
            return result;
        }

        // 寻找左边界
        int first = findBound(nums, target, true);

        // 如果连左边界都没找到，说明数组中不存在该目标值，直接返回 [-1, -1]
        if (first == -1) {
            return result;
        }

        // 寻找右边界
        int last = findBound(nums, target, false);

        result[0] = first;
        result[1] = last;
        return result;
    }

    // 辅助方法：找左边界或右边界
    // isFirst 为 true 时找左边界，为 false 时找右边界
    private int findBound(int[] nums, int target, boolean isFirst) {
        int left = 0;
        int right = nums.length - 1;
        // 记录找到的边界位置，初始化为 -1
        int bound = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                // 找到了一个目标值，先记录下来
                bound = mid;
                // 根据 isFirst 决定接下来的搜索方向
                if (isFirst) {
                    right = mid - 1; // 找第一个，继续向左逼近
                } else {
                    left = mid + 1;  // 找最后一个，继续向右逼近
                }
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return bound;
    }
}

时间复杂度：O(log⁡n)O(\log n)

空间复杂度：O(1)O(1)

评论