首页 > 代码库 > Search for a Range
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，算法大致流程是先二分查找target，找不到直接返回[-1,-1]，找到则在左半部分二分查找第一个等于target的数，在右半部分二分查找第一个大于target的数
1 class Solution { 2 public: 3 vector<int> searchRange(int A[], int n, int target) { 4 vector<int> ans(2, -1); 5 if( !A || n<1 ) return ans; 6 int left = 0, right = n-1; 7 while( left <= right ) { 8 int mid = left + (right-left) / 2; 9 if( target == A[mid] ) {10 ans[0] = lower_bound(A, left, mid-1, target);11 ans[1] = upper_bound(A, mid+1, right, target)-1;12 return ans;13 }14 if( target > A[mid] ) left = mid+1;15 else right = mid-1;16 }17 return ans;18 }19 20 int lower_bound(int A[], int left, int right, int target) { //找到第一个等于target的数21 while( left <= right ) {22 int mid = left + (right-left) / 2;23 if( target > A[mid] ) left = mid+1;24 else right = mid-1;25 }26 return right + 1;27 }28 29 int upper_bound(int A[], int left, int right, int target) { //找到第一个大于target的数30 while( left <= right ) {31 int mid = left + (right-left) / 2;32 if( target >= A[mid] ) left = mid+1;33 else right = mid-1;34 }35 return left;36 }37 };
Search for a Range
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。