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.

思路：这题用分治。

主要方法是，判断区间两端以及中点处三个数的大小。

一共有3种情况：

1）nums[left] < nums[mid] < nums[right]，很明显，这种情况下是没有rotate的，nums[left]就是最小。

2）nums[right] < nums[left] < nums[mid], 这种情况下断层在右半区间内。

3) nums[left] > nums[right] > nums[mid], 这种情况下断层在左半区间内。

算法复杂度为O(logn)

1 class Solution { 2 public: 3     int findRes(int left, int right, vector
     
      & nums) 4     { 5         if (left == right) return nums[left]; 6         int mid = (left + right) >> 1; 7         if (mid == left) 8             return nums[mid] < nums[right] ? 9                 nums[mid] : nums[right];10         if (nums[left] < nums[mid] && nums[mid] > nums[right])11             return findRes(mid + 1, right, nums);12         else if (nums[left] < nums[mid] && nums[mid] < nums[right])13             return nums[left];14         else15             return findRes(left, mid, nums);16     }17     int findMin(vector
      
       & nums) {18         return findRes(0, nums.size() - 1, nums);19     }20 };