剑指 Offer 11. 旋转数组的最小数字
leetcode题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
示例 2：
输入：[2,2,2,0,1]
输出：0
解题思路：
1.首先需要了解什么是旋转数组。 关于旋转数组指的是
把一个有序数组的末尾一部分移动到数组的头部
。这个有序数组在题目中是可以有重复元素的。举个比例，比如数组[1,2,2,3,4,5]，将数组尾部的[3,4,5]移动到头部，即[3,4,5,1,2,2]，它就是元素组的旋转数组。
2.暴力解法
旋转数组是有序的，可以把它看成是两段升序的数组。比如题中的[3,4,5,1,2] 可以看作是[3,4,5]，[1,2]两个数组。那么从数组的头部开始遍历，
直到index的下一个元素index+1比它小
的时候，它一定是整个数组的最小值。只需要
返回arr[index+1]
就可以得到解。这样时间复杂度是线性的，具体的来说是O(index)的。
3.看成是求有序数组的最小值。 其实这道题就是求一个数组升序排序后的头部元素。
使用系统提供的api然后返回arr[0]也可以直接解决
，但这违背了算法的思想。
4.使用二分法
二分搜索一般使用在一个有序的数组中，旋转数组可以看作是两段有序的数组。如题利用二分搜索的思想为数组[3,4,5,1,2]设置三个指针分别指向左侧，右侧和中间。
每一次让中间和最右侧数做比较，如图
arr[mid]>arr[right]
，那么在闭区间[left,mid]中的所有元素一定全部都是大于right所在元素的。那么需要寻找的最小值一定在闭区间[mid+1,right]里。新的查找范围更新
left=mid+1
，这是因为5已经大于2了，没必要在进行判断。
同理： 在如上图的例子中，
arr[mid]<arr[right]
，那么在[mid+1，right]的闭区间一定都是大于arr[mid]的，那么下一次的查找范围是[left,mid]。此时应该
更新right=mid
，对于二分搜索法比较熟悉的话，可能会想到不应该是更新right = mid-1吗？但是在
这里的arr[mid]只是比arr[right]小
，上图的例子就刚好是arr[mid]的特殊情况，如果从[left,mid-1]向前搜索的话，就无法找到最小值。
需要注意的是，上面是没有重复元素的情况，如果存在重复元素的旋转数组呢？
如上图的两种情况都是
arr[mid] ==arr[right]
，此时就无法判断到底是向前取区间或者向后取区间。
所以当arr[mid] ==arr[right]时，
right--
那么相应的mid的位置也会发生变化，再次比较发现arr[mid]<arr[rigth]。这时就回到了上一步，取前面的区间。最终当left=right时，就找到了目标值，此时返回arr[left]。
最终的代码实现
class Solution {
public int minArray(int[] numbers) {
int left = 0;
int right = numbers.length - 1;
if (right == 0)
return numbers[0];
while (left < right) {
int mid = (right - left) / 2 + left;
if (numbers[mid] == numbers[right])
right--;
else if (numbers[mid] > numbers[right])
left = mid + 1;
else if (numbers[mid] < numbers[right])
right = mid;
}
return numbers[left];
}
}
此外，解决这道问题同时可以解决leetcode154号问题，他们是一样的：154. 寻找旋转排序数组中的最小值 II