LeetCode Search for a Range：二分查找確定目標值區間

解法：兩次二分查找

1. 找左邊界：第一個 ≥ target 的位置（lower_bound）
2. 找右邊界：第一個 > target 的位置（upper_bound）減 1
3. 若左邊界值 ≠ target，返回 [-1, -1]

vector searchRange(vector& nums, int target) {
    auto lower = lower_bound(nums.begin(), nums.end(), target);
    if (lower == nums.end() || *lower != target) return {-1, -1};
    auto upper = upper_bound(nums.begin(), nums.end(), target);
    return {int(lower - nums.begin()), int(upper - nums.begin()) - 1};
}

手寫二分（面試常考）

int lowerBound(vector& a, int target) {
    int l=0, r=a.size();
    while (l < r) {
        int m = l + (r-l)/2;
        if (a[m] < target) l = m+1;
        else r = m;
    }
    return l;
}
int upperBound(vector& a, int target) {
    int l=0, r=a.size();
    while (l < r) {
        int m = l + (r-l)/2;
        if (a[m] <= target) l = m+1;
        else r = m;
    }
    return l;
}

複雜度

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