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].
思路：先二分法找最左端，再二分法找最右端。保证稳定排序。具体实现：
二者的结束条件都是start+1==end
class Solution { public: vector< int > searchRange(int A[], int n, int target) { result.clear(); binarySearchLeft(A,-1,n,target); if(result[0]!=-1) binarySearchRight(A,-1,n,target); return result; } void binarySearchLeft(int A[], int start, int end, int target){ //find the first value == target if (start+1 == end){ if(end >= n || A[end]!=target){ result.push_back(-1); result.push_back(-1); } else result.push_back(end); return; } int mid = start + ((end-start)>>1); if (A[mid] < target) binarySearchLeft(A, mid, end, target); else binarySearchLeft(A, start, mid, target); } void binarySearchRight(int A[], int start, int end, int target){ //find the first value == target if (start+1 == end){ result.push_back(start); return; } int mid = start + ((end-start)>>1); if (A[mid] > target) binarySearchRight(A, start, mid, target); else binarySearchRight(A, mid, end, target); } private: vector< int > result; };
34. Search for a Range (Array; Divide-and-Conquer)
原文：http://www.cnblogs.com/qionglouyuyu/p/4853217.html