34. Find First and Last Position of Element in Sorted Array

1.問題

• 給予一個升冪排序過的array, 找出首次出現及最後出現的位置

• 時間複雜度須為O(log n)

• 如果array中沒有target, 則回傳 [-1, -1]

2.想法

• O(log n)暗示使用binary search:

  • 找出target的left bound, 並找出target + 1的left bound -1

3.程式碼

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res;
        if (nums.size() == 0) {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int first = getLowerBound(nums, target, 0, nums.size() - 1); 
        int second = getLowerBound(nums, target + 1, 0, nums.size() - 1) - 1;
        if (first < nums.size() && nums[first] == target) {
            res.push_back(first);
            res.push_back(second);
        } else {
            res.push_back(-1);
            res.push_back(-1);
        }
        return res;
    }
private:
    int getLowerBound(vector<int>& nums, int target, int left, int right)
    {
        if (left > right) {
            return left;
        }
        
        int mid = (left + right) / 2;
        if (nums[mid] < target) {
            return getLowerBound(nums, target, mid + 1, right);
        } else {
            return getLowerBound(nums, target, left, mid - 1);
        }
    }
};