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

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

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

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

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

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

一、核心思想总结       来源：灵茶山艾府

有序数组中目标值的区间 [start, end] 满足两个特征：

1. start 是数组中第一个 ≥ target 的元素下标（目标值的起始位置）；
2. end 是数组中第一个 ≥ target+1 的元素下标 - 1（目标值的结束位置）；
3. 若 start 超出数组范围，或 nums[start] ≠ target，说明目标值不存在，返回 [-1,-1]。

简单理解：把目标值的区间看作「夹在 target 和 target+1 之间」，用两次二分找到这两个边界，就能快速确定目标值的起止位置。

lowbound 方法的核心逻辑：

• 循环中不断缩小范围，最终 left 会停在「第一个大于等于 target 的元素下标」；
• 特殊情况：
  • 若 target 比所有元素大 → left = nums.length（超出数组范围）；
  • 若 target 比所有元素小 → left = 0；
  • 若数组为空 → left = 0（循环不执行，直接返回）。

【背】

right = mid-1 不可以换成break。通过right左移，nums[mid]在变化 带动left变化移动至第一个target

        while(left<=right){
            int mid = (right-left)/2+left;
            if(nums[mid] < target) left = mid+1;
            else right = mid-1;
        }

【完整代码】

class Solution {
    /**
     * 在有序整数数组中查找目标值的第一个和最后一个位置
     * @return 目标值的起始和结束下标，不存在则返回 [-1,-1]
     */
    public int[] searchRange(int[] nums, int target) {
        // 1. 找第一个 >= target 的元素下标（目标值的起始位置）
        int start = lowbound(nums, target);
        // 2. 找第一个 >= target+1 的元素下标，减1即为目标值的结束位置
        int end = lowbound(nums, target + 1) - 1;

        // 3. 判断目标值是否不存在：
        //    - 情况1：start == nums.length → target比所有元素都大（下标越界）
        //    - 情况2：nums[start] != target → 数组中无target（start指向的元素不是target）
        //    注意：必须先判断start是否越界，再访问nums[start]，避免数组下标越界异常
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1};
        }
        // 4. 目标值存在，返回起止下标
        return new int[]{start, end};
    }

     //二分查找：找数组中第一个 >= target 的元素下标（下界查找）
     // return 第一个 >= target 的元素下标；若所有元素都 < target，返回nums.length
    public int lowbound(int[] nums, int target) {
        // 左边界：初始化为数组第一个元素的下标
        int left = 0;
        // 右边界：初始化为数组最后一个元素的下标
        int right = nums.length - 1;

        // 二分查找核心循环：缩小查找范围，直到left > right
        while (left <= right) {
            // 计算中间下标：避免 (left + right) 整数溢出，等价于 (left + right) / 2
            int mid = (right - left) / 2 + left;
            
            if (nums[mid] < target) {
                // 中间值 < 目标值 → 下界在右半区，左边界右移
                left = mid + 1;
            } else {
                // 中间值 >= 目标值 → 下界在左半区（包括mid），右边界左移
                right = mid - 1;
            }
        }
        // 循环结束时，left 即为第一个 >= target 的元素下标
        return left;
    }
}

【灵神NB】

end = lowbound(nums, target + 1) - 1 这也太巧妙了