首页 > 代码库 > [LeetCode] Search for a Range
[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 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 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。