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].

思路

二分查找的变形，不过可能存在数组元素重复的情况，所以在找到元素以后需要和已知的结果进行合并。如果之前没有结果，需要两边都进行查找；如果middle值大于之前的上界，只查找右边区域；如果middle值小于之前的下界，只查找左边区域；未找到的情况和一般的二分类似。代码如下。

代码

 1     vector<int> result;
 2     void initialize(){
 3         result.clear();
 4         result.push_back(-1);
 5         result.push_back(-1);
 6     }
 7     void search(int A[], int left, int right, int target){
 8         if(left >= right)
 9             return;
10         int middle = (left + right)/2;
11         if(A[middle] < target){
12             search(A, middle+1, right, target);
13         }
14         else if(A[middle] > target){
15             search(A, left, middle, target);
16         }
17         else{
18             if(result[0] == -1){
19                 result[0] = middle;
20                 result[1] = middle;
21                 search(A, left, middle, target);
22                 search(A, middle+1, right, target);
23             }
24             else{
25                 if(result[1] <= middle){
26                     result[1] = middle;
27                     search(A, middle+1, right, target);
28                 }
29                 if(result[0] >= middle){
30                     result[0] = middle;
31                     search(A, left, middle, target);
32                 }
33             }
34         }
35     }
36     vector<int> searchRange(int A[], int n, int target) {
37         // Note: The Solution object is instantiated only once and is reused by each test case.
38         initialize();
39         search(A, 0, n, target);
40         return result;
41     }