2089. Find Target Indices After Sorting Array

可以將此題想成在一個排序過的陣列中找到小於等於 target 的 lower_bound。會刻意挑這題是因為用到 binary search 來做，每次在做類似題目的時候，很常花很多的時間去分清楚迴圈的邊界該設定在哪、是要 right > left 就好還是 right >= left、包含找到的條件也是。

而在這篇中給出很清楚的解釋，有點類似二分法的定式，即 left 是不滿足條件的元素，right 是滿足條件的元素(包含num[right])。可以整理出下面這個 template。

vector<int> nums; // an array is sorted in ascending order
int left = -1, right = nums.size();

while(right - left > 1){
    int mid = left + (right - left)/2;

    // the elements which is satisfied the condtion 
    // will be in the right subarray
    if(isOK()){ 
        right = mid;
    }
    else
        left = mid;
}

下面就是這題的程式碼了，可以仔細看一下該滿足條件的是什麼。

class Solution {
public:
    vector<int> targetIndices(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end(), less<int>());
        int left = -1, right = nums.size();

        while(right - left > 1){
            int mid = left + (right - left)/2;
            if(nums[mid] >= target){
                right = mid;
            }
            else
                left = mid;
        }
        vector<int> indices;
        for(size_t i=right; i<nums.size() && nums[i] == target; i++){
            indices.push_back(i);
        }
        return indices;
    }
};

需要注意的是，這裡的left 設定成 -1 而不是 0 ，是因為 target < nums[0] 的時候 nums[0] 應該要在 right 一側，但如果設定成 left=0 則 nums[0] 會在 left 這一側，所以要把邊界往左邊推一個。

Time Complexity: (n*log n)
Space Complexity: O(n)