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 };
原文：http://www.cnblogs.com/bugfly/p/4007035.html