已知一个长度为 n 的数组，预先按照升序排列，经由 1 到 n 次 旋转 后，得到输入数组。例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2] - 若旋转
7次，则可以得到[0,1,2,4,5,6,7]
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
给你一个元素值 互不相同 的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入： nums = [3,4,5,1,2] 输出： 1 解释： 原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。
示例 2：
输入： nums = [4,5,6,7,0,1,2] 输出： 0 解释： 原数组为 [0,1,2,4,5,6,7] ，旋转 4 次得到输入数组。
示例 3：
输入： nums = [11,13,15,17] 输出： 11 解释： 原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。
采用二分法解答这个问题，
Mid = low + (high - low)/2
需要考虑三种情况：
(1) array[mid] > array[high]:
出现这种情况的 array 类似[3,4,5,6,0,1,2]，此时最小数字一定在 mid 的右边。
Low = mid + 1
(2) array[mid] == array[high]:
出现这种情况的 array 类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在 mid 左边
还是右边, 这时只好一个一个试，
High = high - 1
(3) array[mid] < array[high]:
出现这种情况的 array 类似[2,2,3,4,5,6,6], 此时最小数字一定就是 array[mid]或者在 mid 的左
边。因为右边必然都是递增的。
High = mid
注意这里有个坑：如果待查询的范围最后只剩两个数，那么 mid 一定会指向下标靠前的数字
比如 array = [4,6]
Array[low] = 4 ;array[mid] = 4 ; array[high] = 6 ;
如果 high = mid - 1，就会产生错误，因此 high = mid
但情形 (1)中 low = mid + 1 就不会错误
public int findMin(int[] nums) {
//使用二分查找
//考虑到数组中可能存在重复元素，因此使用左闭右开区间
//共有三种情况
//1.如果nums[mid]>nums[right]，说明最小值在右边，left = mid + 1
//2.如果nums[mid]<nums[right]，说明最小值在左边，right = mid
//3.如果nums[mid] == nums[right]，此时无法判断最小值在左边还是右边，但是可以确定的是nums[right]不是最小值，因此可以right--
int left = 0;
int right = nums.length - 1;
while (left<right){
int mid = left + (right - left)/2;
if(nums[mid]>nums[right]){
left = mid + 1;
}
else if(nums[mid]<nums[right]){
right = mid;
}
else{
right--;
}
}
return nums[left];
}