1.问题

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

2.思路

因为所有的数据有类似345122这样的数据规则，最小值1前面的数据部分大于后面的所有数据

使用二分法，每次找出最中间的数据middle和尾部的数据last比较，因为数据是按规则排序好的，以此可以判断最小值在middle前面还是后面

3.代码

package test1_10;
/* * @author qianliu on 2019/4/9 17:04 * @Discription: * 1.问题：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 * 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 */
public class Test6 {

    /* * @author qianliu on 2019/4/10 12:46 * @param [array] * @return int * @Discription: * 1.通过二分查找，如果中间的数大于array[0]，说明最小的数还在后面， * 如果中间的数小于array[lenth-1]，说明最小的数在前面 */
    public int minNumberInRotateArray(int [] array) {

        //数组长度为0，直接返回0
        if (array.length == 0)
            return 0;

        //从first和last和中间值middle对比
        int first = 0;
        int last = array.length-1;


        while (first<last){

            int middle = (first+last)/2;

            //1.最小值在后半段
            if(array[middle] > array[last]){
                //first变化，last不变
                first = middle+1;
            }
            //3.排除一种可能，3333123或者1233333这种情况下
            else if(array[middle] == array[last]){
                last--;
            }
            //2.最小值在前半段
            else {
                //first不变，last变化
                //此处不可以使用last = middle-1，因为3214567,如果1是middle就会出现bug
                last = middle;
            }
        }
        return array[first];
    }

    public static void main(String[] args) {
        int array[] = {3,4,5,1,2};
        System.out.println(new Test6().minNumberInRotateArray(array));
    }
}