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

题目链接：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

代码

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 * https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
 */

function searchRange(nums: number[], target: number): number[] {
    const start = lowerBound(nums, target);
    if (start === nums.length || nums[start] !== target) {
        return [-1, -1]; // nums 中没有 target
    }
    // 如果 start 存在，那么 end 必定存在
    const end = lowerBound(nums, target + 1) - 1;
    return [start, end];
}

// lowerBound 返回最小的满足 nums[i] >= target 的下标 i
// 如果数组为空，或者所有数都 < target，则返回 nums.length
// 要求 nums 是非递减的，即 nums[i] <= nums[i + 1]
function lowerBound(nums: number[], target: number): number {
    let left = -1, right = nums.length; // 开区间 (left, right)
    while (left + 1 < right) { // 区间不为空
        // 循环不变量：
        // nums[left] < target
        // nums[right] >= target
        const mid = Math.floor((left + right) / 2);
        if (nums[mid] >= target) {
            right = mid; // 范围缩小到 (left, mid)
        } else {
            left = mid; // 范围缩小到 (mid, right)
        }
    }
    // 循环结束后 left+1 = right
    // 此时 nums[left] < target 而 nums[right] >= target
    // 所以 right 就是第一个 >= target 的元素下标
    return right;
}

思路

二分查找

本题要求在有序数组中查找目标值的起始和结束位置，时间复杂度要求 $O(\log n)$，因此使用二分查找。

核心思路是利用 lowerBound 函数两次：

1. 查找起始位置：使用 lowerBound(nums, target) 找到第一个 >= target 的位置

   • 如果该位置不存在或值不等于 target，说明数组中没有 target，返回 [-1, -1]

2. 查找结束位置：使用 lowerBound(nums, target + 1) - 1 找到最后一个等于 target 的位置

   • lowerBound(nums, target + 1) 返回第一个 > target 的位置，减 1 即为最后一个等于 target 的位置

lowerBound 函数：返回最小的满足 nums[i] >= target 的下标 i

• 使用开区间 (left, right) 进行二分查找

• 循环不变量：nums[left] < target 且 nums[right] >= target

• 当 left + 1 = right 时循环结束，此时 right 即为答案

• 时间复杂度 $O(\log n)$

• 空间复杂度 $O(1)$