首页 > 代码库 > [LeetCode] Search for a Range

[LeetCode] Search for a Range

2024-07-08 21:16:18   228人阅读

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          else13             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          else29             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         else51         {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          else27             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         else47         {48             result.push_back(m_low);49             result.push_back(m_high);50         }51         52         return result;53     }54 };

 


联系
我们