1 題目

??找到目標出現的區間范圍（Search for a range）

lintcode：題號——61，難度——medium

2 描述

??給定一個包含 n 個整數的排序數組，找出給定目標值 target 的起始和結束位置。如果目標值不在數組中，則返回[-1, -1]。

??樣例1：

輸入：數組 = []，target = 9
輸出：[-1,-1]
解釋：

9不在數組中。

??樣例2：

輸入：數組 = [5, 7, 7, 8, 8, 10]，target = 8
輸出：[3,4]
解釋：

數組的[3,4]子區間值都為8。

3 思路

??在已排序的數組中，尋找目標出現的范圍，找到目標出現的初始和最后位置^[1]，它們中間的區間即是目標區間，二分搜索套模版^[2]，跑兩次就能得到結果。

1. 找到目標出現的初始位置；
2. 找到目標出現的最后位置；
3. 得到目標區間。

3.1 圖解

輸入：數組 = [5, 6, 7, 9, 9, 9, 10, 12]，target = 9
輸出：[3,5]
解釋：

數組的[3,5]子區間值都為8。

3.2 時間復雜度

??在n規模的問題上使用兩次二分法，時間復雜度為O(2 * log n)，依然是O(log n)。

3.3 空間復雜度

??算法的空間復雜度為O(1)。

4 源碼

??C++版本：

/**
* @param A: 已排序數組
* @param target: 目標值
* @return: 目標出現的區間范圍
*/
vector<int> searchRange(vector<int> &A, int target) {
    // write your code here
    vector<int> result;
    if (A.empty())
    {
        result.push_back(-1);
        result.push_back(-1);
        return result;
    }

    int startPos = -1;
    int endPos = -1;
    startPos = findFirstPos(A, target);
    endPos = findLastPos(A, target);
    result.push_back(startPos);
    result.push_back(endPos);

    return result;
}

int findFirstPos(vector<int> & A, int target)
{
    int start = 0;
    int end = A.size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (A.at(mid) >= target)
        {
            end = mid;
        }
        if (A.at(mid) < target)
        {
            start = mid;
        }
    }

    if (A.at(start) == target)
    {
        return start;
    }
    if (A.at(end) == target)
    {
        return end;
    }

    return -1;
}

int findLastPos(vector<int> & A, int target)
{
    int start = 0;
    int end = A.size() - 1;
    int mid = 0;
    while (start + 1 < end)
    {
        mid = start + (end - start) / 2;
        if (A.at(mid) <= target)
        {
            start = mid;
        }
        if (A.at(mid) > target)
        {
            end = mid;
        }
    }

    if (A.at(end) == target)
    {
        return end;
    }
    if (A.at(start) == target)
    {
        return start;
    }

    return -1;
}