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

方法一：

参见STL lower_bound 和 upper_bound http://www.cnblogs.com/diegodu/p/3795077.html

，STL的equal_range就是基于lower_bound 和 upper_bound实现的，这里我们也可以利用这两个函数。。

注意没有找到目标时的判断，low == n表示所有元素都比targe大，A[low] != target且low！=n表示所有元素都比target小。。

 1 int lower_bound(int* array, int low, int high, int key )
 2 {
 3     int mid = 0;
 4     while(low < high)
 5     {   
 6         mid =  (low + high)/2;
 7         //cout << "low :" << low <<endl;
 8         //cout << "high:" << high<<endl;
 9         //cout << "mid:" << mid<<endl;
10         if(array[mid] >= key)
11              high = mid;
12          else
13             low = mid+1;
14     
15     }   
16     return high;
17 
18 }
19 
20 int upper_bound(int* array, int low, int high, int key )
21 {
22     int mid = 0;
23     while(low < high)
24     {   
25         mid =  (low + high)/2;
26         if(array[mid] > key)
27              high = mid;
28          else
29             low = mid+1;
30 
31     }
32     return high;
33 
34 }
35 
36 
37 class Solution {
38 public:
39     vector<int> searchRange(int A[], int n, int target) {
40 
41         int low = lower_bound(A, 0, n, target);
42         int high = upper_bound(A, 0, n, target);
43         vector<int> result;
44 
45         if(low == n || A[low] != target)
46         {
47         result.push_back(-1);
48         result.push_back(-1);
49         }
50         else
51         {
52         result.push_back(low);
53         result.push_back(high-1);
54         }
55         
56         return result;
57     }
58 };

方法二：

利用二分法：

 1 class Solution {
 2 public:
 3     int m_low;
 4     int m_high;
 5 void search(int* array, int low, int high, int key )
 6 {
 7     int mid = 0;
 8 
 9     while(low <= high)
10     {   
11         mid =  (low + high)/2;
12 
13         if(array[mid] == key)
14         {
15             if(mid < m_low)
16                 m_low = mid;
17             if(mid > m_high)
18                 m_high = mid;
19             search(array, low, mid-1, key);
20             search(array, mid+1, high, key);
21             return;
22         }
23         else if(array[mid] > key)
24             
25              high = mid - 1;
26          else
27             low = mid+1;
28     
29     }   
30 
31 }
32     vector<int> searchRange(int A[], int n, int target) {
33 
34         vector<int> result;
35         
36         m_low = INT_MAX;
37         m_high = INT_MIN;
38 
39         search(A, 0, n-1, target);
40         
41         if(m_low == INT_MAX)
42         {
43             result.push_back(-1);
44             result.push_back(-1);
45         }
46         else
47         {
48             result.push_back(m_low);
49             result.push_back(m_high);
50         }
51         
52         return result;
53     }
54 };