61. Search for a Range【medium】

Given a sorted array of n integers, find the starting and ending position of a given target value.

If the target is not found in the array, return [-1, -1].

Have you met this question in a real interview? 

Yes

Example

Given [5, 7, 7, 8, 8, 10] and target value 8,

return [3, 4].

Challenge 

O(log n) time.

 

解法一：

1 class Solution { 2 public: 3     /* 4      * @param A: an integer sorted array 5      * @param target: an integer to be inserted 6      * @return: a list of length 2, [index1, index2] 7      */ 8     vector
       
         searchRange(vector
        
          &A, int target) { 9         if (A.empty()) {10             return vector
         
          (2, -1);11         }12         13         vector
          
            result;14         15         //find first16         int start = 0;17         int end = A.size() - 1;18         19         while (start + 1 < end) {20             int mid = start + (end - start) / 2;21             if (A[mid] == target) {22                 end = mid;23             }24             else if (A[mid] < target) {25                 start = mid;26             }27             else if (A[mid] > target) {28                 end = mid;29             }30         }31         32         if (A[start] == target) {33             result.push_back(start);34         }35         else if (A[end] == target) {36             result.push_back(end);37         }38         else {39             return vector
           
            (2, -1);40         }41         42         //find last43         start = 0;44         end = A.size() - 1;45         46         while (start + 1 < end) {47             int mid = start + (end - start) / 2;48             if (A[mid] == target) {49                 start = mid;50             }51             else if (A[mid] < target) {52                 start = mid;53             }54             else if (A[mid] > target) {55                 end = mid;56             }57         }58         59         if (A[end] == target) {60             result.push_back(end);61         }62         else if (A[start] == target) {63             result.push_back(start);64         }65         66         return result;67     }68 };