假设一个排好序的数组在其某一未知点发生了旋转（比如0 1 2 4 5 6 7 可能变成4 5 6 7 0 1 2）。你需要找到其中最小的元素。
在线评测地址：LintCode 领扣
样例 1:
输入：[4, 5, 6, 7, 0, 1, 2]
输出：0
解释：
数组中的最小值为0
样例 2:
输入：[2,1]
输出：1
解释：
数组中的最小值为1
解题思路
- 最直接的是暴力解法，搜索整个数组找到最小元素，时间复杂度为O(n)。
我们可以旋转数组的特性，用改进后的二分查找来解决，时间复杂度为O(logn)。
算法流程
使用二分法来寻找最小值，如图所示可以帮助我们理解算法过程。
设置双指针left和right指向数组nums两端。
第一次分类讨论：比较nums[left]和nums[right]
如果nums[left] < nums[right]，说明数组没有旋转过，仍然是升序排列。我们直接return nums[left]。
反之，说明数组非单调，进入到第二次分类讨论。
第二次分类讨论：比较nums[left]和nums[mid]，其中mid是二分中点。
如果nums[left] > nums[mid]，可以证明此时数组右半边是升序的，那我们就不用考虑右半边了。最小值一定在[left, mid]间，令right = mid。
如果nums[left] <= nums[mid]，可以证明此时数组左半边是升序的，于是我们不需要考虑左半边。最小值一定在(mid, right]间，令left = mid + 1。
直到left == right时，此时指向的就是最小值，return nums[left]。
等效方法
上述算法中，第二次分类讨论我们比较的是nums[left]和nums[mid]的大小关系，其实比较nums[right]和nums[mid]的大小也是一样的。
nums[left] > nums[mid]，等效于nums[mid] < nums[right]
nums[left] <= nums[mid]，等效于nums[mid] > nums[right]
有兴趣可以证明一下。代码如何实现，看个人的preference啦。
复杂度分析
时间复杂度: O(log(n))，n为nums的长度。同二分查找的时间复杂度。
空间复杂度: $O(1) $。没有使用额外空间。
public class Solution {
/**
* @param nums: a rotated sorted array
* @return: the minimum number in the array
*/
public int findMin(int[] nums) {
int left = 0, right = nums.length - 1;
// 二分法
while (left < right){
// 最小值在left
if (nums[left] < nums[right]){
return nums[left];
}
int mid = left + (right - left) / 2;
// 最小值在[left, mid]
if (nums[left] > nums[mid]){
right = mid;
}
// 最小值在(mid, right]
else{
left = mid + 1;
}
}
return nums[left];
}