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

✨核心逻辑

本题要求时间复杂度为 O(log n)，因此采用 二分查找 策略：

寻找左边界：利用二分查找寻找数组中 第一个大于等于 target 的元素索引。如果找到的这个元素不等于 target，说明数组中不存在目标值，直接返回 [-1, -1]。
寻找右边界：利用二分查找寻找数组中 第一个大于等于 target + 1 的元素索引（相当于寻找 target 的右边界插入点）。那么 target 出现的最后位置就是该索引值减 1。
边界检查：在找到左边界后，必须判断索引是否越界，或者该索引上的值是否与 target 相等，以此确认目标值是否存在。

🔥代码实现（含详细变量注释）

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // target_right：用于第二遍二分查找，寻找 target 的右边界。
        // 注意：当 target 为 Integer.MAX_VALUE 时，target + 1 会导致整数溢出，变成 Integer.MIN_VALUE，实际应用中需小心防范。
        int target_right = target + 1;
        
        // left0、right0：第一遍二分查找（找左边界）的左右指针
        int left0 = 0;
        int right0 = nums.length - 1;
        // left1、right1：第二遍二分查找（找右边界的下一位）的左右指针
        int left1 = 0;
        int right1 = nums.length - 1;

        // 第一遍二分：寻找 >= target 的最左侧位置
        while (left0 <= right0) {
            // mid0：防止溢出的中间索引计算方式
            int mid0 = left0 + (right0 - left0) / 2;
            if (nums[mid0] >= target) {
                right0 = mid0 - 1; // 如果当前位置大于等于 target，说明左边界在当前位置或更左边，收缩右边界
            } else {
                left0 = mid0 + 1;  // 如果当前位置小于 target，说明左边界在右侧，收缩左边界
            }
        }
        // answer0：最终找到的第一个 >= target 的索引
        int answer0 = left0;

        // 边界检查：如果目标不存在（索引越界，或者对应元素不是 target），直接返回 -1
        if (answer0 >= nums.length || nums[answer0] != target) {
            return new int[]{-1, -1};
        }

        // 第二遍二分：寻找 >= target_right 的最左侧位置
        while (left1 <= right1) {
            // mid1：防止溢出的中间索引计算方式
            int mid1 = left1 + (right1 - left1) / 2;
            if (nums[mid1] >= target_right) {
                right1 = mid1 - 1; // 如果大于等于 target_right，收缩右边界
            } else {
                left1 = mid1 + 1;  // 如果小于 target_right，收缩左边界
            }
        }
        // answer1：最后一个 target 的索引，就是第一个 >= target_right 的索引减 1
        int answer1 = left1 - 1;

        // 返回找到的左右边界数组
        return new int[]{answer0, answer1};
    }
}

⏱️复杂度分析
- 时间复杂度：O(log N)，其中 N 是数组的长度。我们执行了两次二分查找，每次都将搜索区间缩小一半，因此整体时间复杂度为对数级别。
- 空间复杂度：O(1)，仅使用了 left0、right0、left1、right1、mid0、mid1 等常数个额外的整型变量，没有占用额外的数组或递归栈空间。