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

» Solve this problem


[解题思路]
首先二分，然后根据二分的坐标分别往前和往后找找即可。

[Code]

1:       vector<int> searchRange(int A[], int n, int target) {  
2:            // Start typing your C/C++ solution below  
3:            // DO NOT write int main() function  
4:            vector<int> range;  
5:            int index = searchTarget(A, 0, n-1, target);  
6:            if(index == -1)  
7:            {  
8:                 range.push_back(-1);  
9:                 range.push_back(-1);  
10:            }  
11:            else  
12:            {  
13:                 int is = index;  
14:                 while(is>0 && A[is-1] == A[index]) is--;  
15:                 int ie = index;  
16:                 while(ie<n-1 && A[ie+1] == A[index]) ie++;  
17:                 range.push_back(is);  
18:                 range.push_back(ie);        
19:            }  
20:            return range;  
21:       }  
22:       int searchTarget(int A[], int start, int end, int target)  
23:       {  
24:            if(start > end) return -1;  
25:            int mid = (start+end)/2;  
26:            if(A[mid] == target) return mid;  
27:            if(A[mid]<target)  
28:            return searchTarget(A, mid+1, end, target);  
29:            else  
30:            return searchTarget(A, start, mid-1, target);      
31:       }  

[Note]
1. Line 6
错误的写成，"if(index = -1)", 少了个=号，结果老是输出[-1,-1].


Update: 07/15/2013 Refactor the code
看了一下评论，Jarvis很关注最差时间复杂度。其实从题目上来说，它更关注是平均复杂度。上面的算法在最差情况下复杂度是O(n)，但是平均复杂度是O(lgn)。
如果想实现最差复杂度也是O(lgn)，也很简单，做两次二分就可以了，第一次二分找出最左边的边界，第二次二分找出最右边的边界，这样，无论平均还是最差都是O(lgn)。

实现如下：

1:    vector<int> searchRange(int A[], int n, int target) {  
2:      vector<int> result;  
3:      result.push_back(-1);  
4:      result.push_back(-1);    
5:      // find the low bound of the range, O(lgn)  
6:      int start =0, end =n-1;  
7:      while(start < end)  
8:      {  
9:        int mid = (start + end)/2;  
10:        if(A[mid] < target)  
11:        {  
12:          start = mid + 1;  
13:          continue;  
14:        }  
15:        end = mid;  
16:      }      
17:      int low_bound = A[start] == target? start:-1;  
18:      if(low_bound == -1)  
19:      {  
20:        return result;  
21:      }  
22:      // find the high bound of the range, O(lgn)  
23:      start =low_bound, end =n;  
24:      while(start < end)  
25:      {  
26:        int mid = (start + end)/2;  
27:        if(A[mid] > target)  
28:        {  
29:          end = mid;  
30:          continue;  
31:        }            
32:        start = mid+1;  
33:      }  
34:      int high_bound = start-1;  
35:      result.clear();  
36:      result.push_back(low_bound);  
37:      result.push_back(high_bound);  
38:      return result;      
39:    }