題目網址：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

題意：給一按照非遞減順序排列的整數array nums, 和一個整數 target。請找出給定 target 在 nums 中的開始位置和結束位置。

如果 nums 中不存在 target, 則返回 [-1, -1]。

設計 $O(log(n))$ time 的演算法。

Solution：

想法：利用 Binary Search

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        const int lower = firstPos(nums, target);
        const int upper = lastPos(nums, target);
        return {lower, upper};
    }

private:
    int firstPos(const vector<int>& nums, const int target){
        const int n = nums.size();
        int left = 0, right = n - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;

            // mid 右側元素皆 >= target, 故往左邊尋找
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // left 越界 or nums[left] 不為 target, 則返回 -1
        return (left == n || nums[left] != target) ? -1 : left;
    }

    int lastPos(const vector<int>& nums, const int target){
        const int n = nums.size();
        int left = 0, right = n - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;

            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        --left; // left 為第一個 > target 的數, 而 left - 1 為最後一個 <= target 的數

        return (left < 0 || nums[left] != target) ? -1 : left;
    }
};
  • time：$O(log(n))$ ➔ Binary Search 的時間複雜度
  • space：$O(1)$ ➔ 只需常數空間