[剑指offer][Java]旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

程序核心思想

看到题目是一个非减的排序了的数组，并且只经过一次旋转，所以对于这种基本已经有序的数组，可以采用二分法，找到其中最小的那个数。
比如3,4,5,1,2是一个旋转，用二分查找来做，如果mid指向的数比max指向的数要大，说明进行了旋转的部分一定在mid右边，所以让min=mid+1；如果mid指向的数比max指向的数要小，说明进行了旋转的部分一定在mid的左边，所以让max=mid，这个地方我查了好久的错，我写的是max=mid-1，原因是如果mid碰巧是要找的（旋转点），它满足比max小，所以如果直接让max=mid-1，就会错过旋转点，这是因为题目让找的是最小值；如果让找最大值呢？mid如果比max小，则max=mid-1；如果mid比max大，那么min=mid。具体问题具体分析。

Tips

因为经过指针的移动，会出现max<min的情况，这个时候就不好判断正确答案了。我的方法是，经过分析，只允许出现两种情况，第一种min=max，结果输出min和max是一样的；第二种：max如果比min小的话，只会比min小1，所以如果检测到max<min，那么令max++或min--（看是max主动减小的，还是min主动增大的），使得min=max，最终输出结果。如果max>min，就要继续二分，直到max=min或max<min（按上述办法处理，使其最后相等）。

代码

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length == 0)    return 0;
        if(array[0] < array[array.length-1])    return array[0];
       
        int min = 0;
        int max = array.length-1;
        int mid = (min+max)/2;
        
        while(max > min){
            if(array[mid] > array[max]){
                min = mid + 1;
                if(min > max){
                    min--;
                    break;
                }
                mid = (min+max)/2;
            }else{
                max = mid;
                if(max < min){
                    max++;
                    break;
                }
                mid = (min+max)/2;
            }
        }

        return array[max];
    }
}