Find Minimum in Rotated Sorted Array

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<int>& 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         else
15             return findRes(left, mid, nums);
16     }
17     int findMin(vector<int>& nums) {
18         return findRes(0, nums.size() - 1, nums);
19     }
20 };