LeetCode[Array]: Search for a Range

LeetCode[Array]: Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

我的解題思路是：首先用二分查找找到目標元素，然後在縮小後的搜索區域的前半部分利用二分查找找到起點，在後半部分利用二分查找找到終點。

我的C++代碼實現如下：

vector searchRange(int A[], int n, int target) {
    vector range(2, -1);
    int start = 0, end = n - 1;
    while (start <= end) {
        int mid = (start + end) >> 1;
        if (A[mid] == target) {
            int start1 = start, end1 = mid;
            while (start1 <= end1) {
                int mid1 = (start1 + end1) >> 1;
                if (A[mid1] == target) end1 = mid1 - 1;
                else start1 = mid1 + 1;
            }
            range[0] = start1;

            start1 = mid, end1 = end;
            while (start1 <= end1) {
                int mid1 = (start1 + end1) >> 1;
                if (A[mid1] == target) start1 = mid1 + 1;
                else end1 = mid1 - 1;
            }
            range[1] = start1 - 1;

            break;
        }
        else if (A[mid] > target) end = mid - 1;
        else start = mid + 1;
    }

    return  range;
}

我在Discuss上看到一個非常巧妙的解法：

You can choose two double numbers T-0.5 and T+0.5 for target T, and then binary search positions for the two double numbers in the integer array(suppose the position are a and b respectively), then the answer is [a, b-1]. For example, for input [5,7,7,8,8,10], you can search position for number 7.5 and 8.5 using binary-search, and the result is 3 and 5, by which the answer [3,4] is easily obtained.

根據以上思路我做了如下實現：

class Solution {
public:
    vector searchRange(int A[], int n, int target) {
        vector range(2);
        int start = binarySearch(A, n, (double)target - 0.5);
        int end   = binarySearch(A, n, (double)target + 0.5);
        range[0] = (end > start ? start : -1);
        range[1] = (end > start ? end-1 : -1);
        return  range;
    }

private:
    int binarySearch(int A[], int n, double target) {
        int start = 0, end = n - 1;
        while (start <= end) {
            int mid = (start + end) >> 1;
            if ((double)A[mid] > target) end = mid - 1;
            else start = mid + 1;
        }

        return start;
    }
};