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].
Analyse: Binary search.
Runtime: 12ms.
1 class Solution { 2 public: 3 vector<int> searchRange(vector<int>& nums, int target) { 4 vector<int> result; 5 if(nums.size() == 0) return result; 6 7 int left = findLeft(nums, target); 8 int right = findRight(nums, target); 9 10 result.push_back(left); 11 result.push_back(right); 12 13 return result; 14 } 15 16 int findLeft(vector<int> &nums, int target){ 17 int low = 0, high = nums.size() - 1; 18 19 while(low <= high){ 20 int mid = (low + high) / 2; 21 if(nums[mid] < target) low = mid + 1; 22 else high = mid - 1; 23 } 24 if(nums[low] != target) return -1; 25 else return low; 26 } 27 28 int findRight(vector<int> &nums, int target){ 29 int low = 0, high = nums.size() - 1; 30 31 while(low <= high){ 32 int mid = (low + high) / 2; 33 if(nums[mid] > target) high = mid - 1; 34 else low = mid + 1; 35 } 36 if(nums[high] != target) return -1; 37 else return high; 38 } 39 };
原文：http://www.cnblogs.com/amazingzoe/p/4672642.html