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

題目要求

在有序數組中找到目標值的起始和結束位置，時間 O(log n)。不存在返回 [-1, -1]。

標準庫解法：lower_bound / upper_bound

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        auto l = lower_bound(nums.begin(), nums.end(), target);
        if (l == nums.end() || *l != target) return {-1, -1};
        auto r = upper_bound(nums.begin(), nums.end(), target);
        return {int(l - nums.begin()), int(r - nums.begin()) - 1};
    }
};

手寫二分模板（面試必備）

// 第一個 ≥ target 的位置
int lower_bound(const vector& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

// 第一個 > target 的位置
int upper_bound(const vector& a, int target) {
    int lo = 0, hi = a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

關鍵不變量

• lower_bound：循環不變量 [0, lo) < target，[hi, n) ≥ target。
• upper_bound：[0, lo) ≤ target，[hi, n) > target。
• 返回值即為左邊界；右邊界 = upper_bound - 1。

複雜度

• 時間：O(log n)，兩次二分。
• 空間：O(1)。

此題是「二分查找邊界」的標準考點，掌握 lower/upper_bound 寫法可應對所有區間查找變體。