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

在有序数组中查找目标值的范围：基于二分查找的 Java 实现详解

一、引言

在算法和数据结构的领域中，处理有序数组是一个常见的任务。其中，查找目标值在有序数组中的起始和结束位置是一个经典问题。这个问题不仅考察对基本算法的理解，还要求我们设计出高效的解决方案，以满足时间复杂度的限制。本文将详细探讨如何使用 Java 语言，通过二分查找算法来解决这一问题。

二、问题描述

给定一个按照非递减顺序排列的整数数组 nums，以及一个目标值 target。我们的任务是找出目标值 target 在数组 nums 中的开始位置和结束位置。如果数组中不存在目标值 target，则返回 [-1, -1]。并且，算法的时间复杂度必须为 O(log n)，其中 n 是数组 nums 的长度。

三、传统方法的不足

一种直观的解决方法是遍历整个数组，从数组的开头开始，逐个检查元素是否等于目标值。当找到第一个等于目标值的元素时，记录其位置作为开始位置；继续遍历，找到最后一个等于目标值的元素，记录其位置作为结束位置。然而，这种方法的时间复杂度为 O(n)，因为在最坏情况下，需要遍历整个数组。这显然不符合题目中 O(log n) 的时间复杂度要求。

四、二分查找算法简介

二分查找（Binary Search）是一种在有序数组中查找某一特定元素的搜索算法。它的基本思想是将数组分成两部分，然后比较目标值与中间元素的大小。如果目标值等于中间元素，则查找成功；如果目标值小于中间元素，则在数组的左半部分继续查找；如果目标值大于中间元素，则在数组的右半部分继续查找。通过不断地将搜索范围缩小一半，二分查找的时间复杂度为 O(log n)。

五、基于二分查找的解决方案

为了在有序数组中找到目标值的开始和结束位置，我们需要对二分查找算法进行一些扩展。具体来说，我们需要进行两次二分查找：一次用于找到目标值的开始位置，另一次用于找到目标值的结束位置。

以下是 Java 代码实现：

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 首先查找目标值的开始位置
        int start = findStart(nums, target);
        // 如果开始位置为 -1，说明数组中不存在目标值，直接返回 [-1, -1]
        if (start == -1) {
            return new int[]{-1, -1};
        }
        // 然后查找目标值的结束位置
        int end = findEnd(nums, target);
        return new int[]{start, end};
    }

    private int findStart(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int start = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                start = mid;
                // 继续向左查找，以找到目标值的最左侧位置
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return start;
    }

    private int findEnd(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int end = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                end = mid;
                // 继续向右查找，以找到目标值的最右侧位置
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return end;
    }
}

六、代码详细解释

1. searchRange 方法：这是主方法，负责调用 findStart 和 findEnd 方法来查找目标值的开始和结束位置。如果 findStart 方法返回 -1，说明数组中不存在目标值，直接返回 [-1, -1]。否则，返回包含开始和结束位置的数组。
2. findStart 方法：使用二分查找来找到目标值的开始位置。在查找过程中，当 nums[mid] == target 时，将 start 记录为 mid，并将 right 更新为 mid - 1，继续向左查找，以确保找到的是目标值的最左侧位置。
3. findEnd 方法：同样使用二分查找来找到目标值的结束位置。当 nums[mid] == target 时，将 end 记录为 mid，并将 left 更新为 mid + 1，继续向右查找，以确保找到的是目标值的最右侧位置。

七、复杂度分析

1. 时间复杂度：由于进行了两次二分查找，每次二分查找的时间复杂度为 O(log n)，其中 n 是数组的长度。因此，总的时间复杂度为 O(log n)，满足题目要求。
2. 空间复杂度：代码中只使用了常数级别的额外空间，如 left、right、mid、start 和 end 等变量。因此，空间复杂度为 O(1)。

八、总结

通过本文的详细讲解，我们了解了如何使用二分查找算法在有序数组中查找目标值的开始和结束位置。这种方法不仅高效，时间复杂度为 O(log n)，而且实现相对简单。在实际应用中，这种算法可以用于许多场景，如在有序数据集中统计某个值的出现次数等。希望本文能够帮助读者更好地理解和掌握二分查找算法及其应用。