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

題目回顧

同 LeetCode 2906，此處提供遞歸版二分實現。

遞歸二分模板

int searchRangeIndex(vector& nums, int target, int low, int high, bool isLeft) {
    while (low <= high) {
        int mid = (low + high) >> 1;
        if (nums[mid] == target) {
            int temp = -1;
            if (isLeft) {
                if (mid > low && nums[mid-1] == target)
                    temp = searchRangeIndex(nums, target, low, mid-1, true);
            } else {
                if (mid < high && nums[mid+1] == target)
                    temp = searchRangeIndex(nums, target, mid+1, high, false);
            }
            return temp == -1 ? mid : temp;
        } else if (nums[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

調用

vector searchRange(vector& nums, int target) {
    int n = nums.size();
    int left = searchRangeIndex(nums, target, 0, n-1, true);
    int right = searchRangeIndex(nums, target, 0, n-1, false);
    return {left, right};
}

注意

遞歸版雖然邏輯清晰，但最壞情況（全數組相同值）遞歸深度 O(n) 可能棧溢出。面試推薦迭代版 lower_bound/upper_bound 模板。