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

目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

一、问题描述

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

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

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

二、解题思路

• 二分查找 是解决这种时间复杂度要求的最优选择。
• 我们需要找到目标值 target 在数组中的最左边界和最右边界。
• 为了在 O(log⁡n)O(\log n)O(logn) 的时间复杂度内实现这个任务，我们可以两次使用二分查找：
  • 第一次查找 target 的左边界。
  • 第二次查找 target 的右边界。

详细步骤：

• 查找左边界：

  • 使用二分查找，找到 target 出现的最左边的索引位置。如果中间值 nums[mid] 大于或等于 target，则移动 right；否则移动 left，直到找到 target 的最左边界。

• 查找右边界：

  • 类似地，我们使用二分查找找到 target 的最右边的索引位置。如果中间值 nums[mid] 大于 target，则移动 right；如果中间值小于等于 target，则移动 left，直到找到 target 的最右边界。

• 如果数组中不存在 target，直接返回 [-1, -1]。

三、代码

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[2];
        result[0] = findLeft(nums, target);
        result[1] = findRight(nums, target);
        return result;
    }

    // 查找左边界
    private int findLeft(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 检查 left 是否越界且是否是目标值
        if (left < nums.length && nums[left] == target) {
            return left;
        }
        return -1;
    }

    // 查找右边界
    private int findRight(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 检查 right 是否越界且是否是目标值
        if (right >= 0 && nums[right] == target) {
            return right;
        }
        return -1;
    }
}

四、复杂度分析

• 时间复杂度：O(log⁡n)O(\log n)O(logn)。每次二分查找都会将搜索空间减半，因此两个二分查找总的时间复杂度是 O(log⁡n)O(\log n)O(logn)。
• 空间复杂度：O(1)O(1)O(1)。我们只使用了常数空间来存储边界和结果数组。