1 题目解析

34. 在排序数组中查找元素的第一个和最后一个位置要求在一个非递减排序的数组中找到特定元素target的起始位置和结束位置，并且要求的时间复杂度为O(log n)，这提示我们使用二分查找法来解决问题。

2 解题思路

本题需要找到目标值在数组中的第一个和最后一个出现的位置。为了达到 O(log n) 的时间复杂度，我们可以利用二分查找法分别找到目标值的第一个和最后一个出现的位置。

1. 查找目标值：首先使用二分查找找到目标值 target 在数组中的任意位置。
2. 查找第一个位置：从找到的目标值位置出发，向左移动直到找到第一个位置。
3. 查找最后一个位置：从找到的目标值位置出发，向右移动直到找到最后一个位置。

3 Java 代码实现

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int index = binarySearch(nums, target);
        if (index == -1)
            return new int[] { -1, -1 };

        int left = index;
        int right = index;
        // 查找第一个位置
        while (left - 1 >= 0 && nums[left - 1] == target) {
            left--;
        }
        // 查找最后一个位置
        while (right + 1 <= nums.length - 1 && nums[right + 1] == target) {
            right++;
        }
        return new int[] { left, right };
    }

    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] > target)
                right = middle - 1;
            else if (nums[middle] < target)
                left = middle + 1;
            else
                return middle;
        }
        return -1;
    }
}

4 注意事项

• 二分查找：使用二分查找找到目标值 target 的任意位置。
• 边界检查：在查找第一个和最后一个位置时，需要确保不会越界。
• 循环条件：在查找第一个和最后一个位置时，循环条件分别是 left - 1 >= 0 和 right + 1 <= nums.length - 1，以确保不会访问数组之外的元素。

5 优化建议

尽管上述代码能够解决问题，但可以进一步优化为一次二分查找找到目标值的第一个出现位置，然后再进行一次二分查找找到最后一个出现位置。这种方法更加高效，因为每次二分查找都是 O(log n) 的时间复杂度。

6 优化后的Java代码实现

public class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = findLeftBoundary(nums, target);
        int end = findRightBoundary(nums, target);
        return new int[] { start, end };
    }

    private int findLeftBoundary(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        // 检查是否找到目标值
        if (left < nums.length && nums[left] == target) {
            return left;
        }
        return -1;
    }

    private int findRightBoundary(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] <= target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        // 检查是否找到目标值
        if (right >= 0 && nums[right] == target) {
            return right;
        }
        return -1;
    }
}