LeetCode Search for a Range：兩次二分查找左/右邊界

題目回顧

有序數組中找 target 的起始和結束位置。不存在返回 [-1,-1]。要求 O(log n)。
例：[5,7,7,8,8,10], target=8 → [3,4]

核心思路：兩次二分分別找左/右邊界

• 左邊界：最左的 target，條件 nums[mid] == target && (mid==0 || nums[mid-1] != target)
• 右邊界：最右的 target，條件 nums[mid] == target && (mid==n-1 || nums[mid+1] != target)

Python 代碼

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        # 找左邊界
        left, right = 0, n
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target and (mid == 0 or nums[mid-1] != target):
                left = mid
                break
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        if left == n or nums[left] != target:
            return [-1, -1]
        start = left
        
        # 找右邊界
        left, right = 0, n
        while left < right:
            mid = (left + right) // 2
            if nums[mid] == target and (mid == n-1 or nums[mid+1] != target):
                right = mid
                break
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid
        return [start, right]

統一模板：lower_bound / upper_bound

int lower_bound(vector& nums, int target) {
    int l = 0, r = nums.size();
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] < target) l = mid + 1;
        else r = mid;
    }
    return l;
}
int upper_bound(vector& nums, int target) {
    int l = 0, r = nums.size();
    while (l < r) {
        int mid = (l + r) / 2;
        if (nums[mid] <= target) l = mid + 1;
        else r = mid;
    }
    return l - 1;
}
// 用法：
int L = lower_bound(nums, target);
if (L == nums.size() || nums[L] != target) return {-1,-1};
int R = upper_bound(nums, target);
return {L, R};

複雜度

• 時間：O(log n)
• 空間：O(1)