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; } };