Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array.
ERROR: control may reach end of non-void function
1 class Solution { 2 public: 3 int findMin(vector<int>& nums) { 4 if(nums.empty()) return 0; 5 6 return helper(nums, 0, nums.size() - 1); 7 } 8 9 int helper(vector<int>& nums, int left, int right){ 10 if(left == right) return nums[left]; 11 if(right - left == 1) return min(nums[left], nums[right]); 12 13 int mid = left + (right - left) / 2; 14 15 if(nums[left] < nums[right]) //didn‘t rotate 16 return nums[left]; 17 if(nums[mid] > nums[left]) 18 return helper(nums, mid, right); 19 if(nums[mid] < nums[left]) 20 return helper(nums, left, mid); 21 } 22 }; 23 24
1 class Solution { 2 public: 3 int findMin(vector<int>& nums) { 4 if(nums.empty()) return 0; 5 6 return helper(nums, 0, nums.size() - 1); 7 } 8 9 int helper(vector<int>& nums, int left, int right){ 10 if(left == right) return nums[left]; 11 if((right - left) == 1) return min(nums[left], nums[right]); 12 13 int mid = left + (right - left) / 2; 14 15 if(nums[left] < nums[right]) //didn‘t rotate 16 return nums[left]; 17 else if(nums[mid] > nums[left]) 18 return helper(nums, mid, right); 19 else 20 return helper(nums, left, mid); 21 } 22 }; 23 24
Find Minimum in Rotated Sorted Array
原文：http://www.cnblogs.com/amazingzoe/p/4870738.html
