Search for a Range

Search for a Range.png

===================== 解題思路 =====================

這題是個綜合 first position && last position 的題目 基本就是先找 first position 如果沒找到代表根本沒有 target 在裡面 直接回傳 {-1,-1} 如果找到就先存好 res[0] 的值為 first position 接著再跑 last position (特別注意要記得 reset left 跟 right 的值)

===================== C++ code ====================

<pre><code>
class Solution {

/** 
 *@param A : an integer sorted array
 *@param target :  an integer to be inserted
 *return : a list of length 2, [index1, index2]
 */

public:

vector<int> searchRange(vector<int> &A, int target) {
    // find the first position
    vector<int> res(2, -1);
    if(A.size() == 0) return res;
    int left = 0, right = A.size() - 1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(A[mid] >= target) right = mid;
        else left = mid;
    }
    if(A[left] != target && A[right] != target) return res;
    res[0] = A[left] == target? left : right;
    
    //find the last position
    left = 0;
    right = A.size() - 1;
    while(left + 1 < right)
    {
        int mid = left + (right - left) / 2;
        if(A[mid] <= target) left = mid;
        else right = mid;
    }
    res[1] = A[right] == target? right : left;
    return res;
}

};
<code><pre>