LeetCode 34 在排序數組中查找元素的第一和最後位置

題目翻譯

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

二分查找變體

需實現兩次二分：

• 查找左邊界：找到第一個 ≥ target 的位置。
• 查找右邊界：找到最後一個 ≤ target 的位置。

若左邊界 ≤ 右邊界且值均為 target，返回區間；否則返回 [-1, -1]。

標準庫實現（推薦）

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

手寫二分模板

int binarySearchLow(vector<int>& nums, int target, int l, int r) {
    if (l > r) return l;
    int mid = l + (r - l) / 2;
    if (nums[mid] < target) return binarySearchLow(nums, target, mid+1, r);
    else return binarySearchLow(nums, target, l, mid-1);
}
int binarySearchUp(vector<int>& nums, int target, int l, int r) {
    if (l > r) return r;
    int mid = l + (r - l) / 2;
    if (nums[mid] > target) return binarySearchUp(nums, target, l, mid-1);
    else return binarySearchUp(nums, target, mid+1, r);
}

複雜度

時間 O(log n)，空間 O(1) 或 O(log n) 遞歸棧。