剑指offer-----旋转数组的最小数字(java版)

剑指offer-----旋转数组的最小数字(java版)。

一、题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。

二、例子

例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

三、思路
对于数组{3，4，5，1，2}，我们可以使用二分法的思想，使用2个指针，第一个指针指向头，第二个指针指向最后一个元素，可以将原数组看成2个子数组，二分法之后判断中间元素，如果中间元素大于index1的元素，则中间元素（mid）在第一个子数组，最小元素在mid后，如果中间元素小于index2的元素，则中间元素（mid）在第二个子数组，最小元素在mid之前。

对于特殊数组如{1,0,1,1,1,1}，{1,1,1,1,0,1}使用二分法是无效的，因为index1和index2，mid的元素都是相同的，所以对于这种情况只能进行顺序遍历。

四 程序源码

public class Solution {
    public int minNumberInRotateArray(int [] array) {
        if(array.length==0)
            return 0;
        int index1 = 0;
        int index2 = array.length-1;
        int mid = index1;
        while (array[index1]>=array[index2]){
            if (index2 - index1 == 1){
                mid = index2;
                break;
            }
            mid = (index1+index2)>>1;
            if (array[index1] == array[index2]&&array[mid] == array[index1]){
                return find(array,index1,index2);
            }

            if (array[mid]>=array[index1])
                index1 = mid;
            else if(array[mid]<=array[index2])
                index2 = mid;
        }
           return array[mid];
    }

    public int find(int[] array,int index1,int index2){
        int result = array[index1];
        for (int i=index1+1;i<=index2;i++){
            if (result>array[i])
                result = array[i];
        }
        return result;
    }
}