剑指 Offer 11. 旋转数组的最小数字

在 剑指 Offer 53 - II. 0～n-1中缺失的数字 中，我们可以把数组分成 左数组和右数组，很明显这道题也可以分成左右数组，但是在那一道题中，我们可以用索引判断元素是在左数组中还是在右数组中，那么这道题该如何判断呢？

　　声明 left,right 分别为数组的左右两端。m = (left+right)/2 为每次的中点，接下来是判断左右数组的方法：

　　1. 当 numbers[m] > numbers[right] 时，m一定在左数组中（因为左数组一定大于等于右数组的元素），此时转折点应该在 [m+1,right] 之间，因此执行 left = m+1。

　　2. 当 numbers[m] < numbers[right] 时，m一定在右数组中（因为右数组是递增数组），此时转折点应该在 [left,m] 之间，因此执行 right = m。

　　3. 当 numbers[m] = numbers[right] 时，无法判断m在哪个数组中（因为可能在相同的元素中间断开），此时转折点应该在 [left,right]之间（为什么不是 [mid,right]: 因为可能根本就没有转折点，比如 1 3 3），此时中间元素已经很少了，直接遍历就行。

　　如果没有出现第三种情况，最终 left 应该指向 右数组的第一个元素，right 应该指向 左数组的最后一个元素（与 53题相同），因此返回 numbers[left] 即可。

class Solution {
    public int findRes(int[] numbers,int left,int right){
        int min = numbers[left];
        for(int i=left+1;i<=right;i++){
            if(numbers[i]<min){
                min = numbers[i];
            }
        }
        return min;
    } //找到对应的最小值
    public int minArray(int[] numbers) {
        int left = 0,right = numbers.length-1,mid;
        while(left<=right){
            mid = left + (right-left)/2;
            if(numbers[mid] > numbers[right]){
                //在左数组中 [mid+1,right]
                left = mid+1;
            }else if(numbers[mid] < numbers[right]){
                //在右数组中 [left,mid]
                right = mid;
            }else{
                return findRes(numbers,left,right); //返回数组的最小值
            }
        }
        return numbers[left]; //left位置是右数组第一个元素，返回numbers[left]
    }
}