LeetCode 34：Search for a Range - 二分查找首尾位置

問題描述

給定升序數組 nums 和目標值 target，找到目標值的起始和結束位置。若不存在返回 [-1, -1]。要求 O(log n)。

二分查找兩次

1. 找左邊界：mid = (l+r)/2，若 nums[mid] >= target 則 r = mid，否則 l = mid+1。最終 l 為第一個 ≥ target 的位置，檢查是否等於 target。
2. 找右邊界：mid = (l+r+1)/2 (上中位數)，若 nums[mid] <= target 則 l = mid，否則 r = mid-1。最終 r 為最後一個 ≤ target 的位置。

代碼實現

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        // 左邊界
        while (l < r) {
            int mid = (l + r) >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (l == n || nums[l] != target) return {-1, -1};
        int left = l;
        // 右邊界
        l = 0; r = n - 1;
        while (l < r) {
            int mid = (l + r + 1) >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return {left, r};
    }
};

關鍵點

• 左邊界用下取整，右邊界用上取整避免死循環。
• 邊界條件 l < r 而非 l <= r，循環不變量更清晰。
• 先檢查左邊界是否有效，無效直接返回。

總結

標準「二分查找左右邊界」模板。掌握 lower_bound 和 upper_bound 的手寫實現是二分查找進階的關鍵。