1. 题意
假设按升序排序的数组在事先未知的某个点处旋转。（即[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2]）。
找到其中最小值。
假设数组中不存在重复。
2.分析
对于区间nums[lo, hi],
(1) 如果nums[lo] < nums[hi]，此区间是升序的，没有旋转，直接返回nums[lo]即为最小值。
若不满足(1) 则nums[lo] > nums[hi];
(2) 若nums[mi] >= nums[lo]
(nums[mi] >= nums[lo] > nums[hi] ，‘ = ’ 表示两个数的情况，例如[1, 0] 此时lo, mi都指向1的位置)
lo = mi + 1
(3) 若nums[mi] < nums[hi]
(nums[lo] > nums[hi] > nums[mi])
hi = mi；(此时的nums[mi]，可能是最小值)
3.实现
class Solution {
public:
int findMin(vector<int>& nums) {
if(nums.empty())
return 0;
int lo = 0;
int hi = nums.size() - 1;
while(lo < hi)
{
if(nums[lo] < nums[hi])
return nums[lo];
int mi = lo + (hi - lo) / 2;
if(nums[mi] >= nums[lo])
lo = mi + 1;
else if(nums[mi] < nums[hi])
hi = mi;
}
return nums[lo];
}
};
