剑指Offer——旋转数组的最小数字

1、题目描述

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

2、代码实现

package com.baozi.offer;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
 * 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 * NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
 *
 * @author BaoZi
 * @create 2019-07-11-10:07
 */
public class Offer6 {
    public static void main(String[] args) {
        int[] array = new int[]{3, 4, 5, 1, 2};
        Offer6 offer6 = new Offer6();
        int reslut = offer6.minNumberInRotateArray(array);
        System.out.println(reslut);
    }

    // 这里使用了二分查找的思想，查找效率肯定要比遍历查找的效率高的多。
    public int minNumberInRotateArray(int[] array) {
        //1、先判断数组为特殊情况的时候（检查边界值）
        if (array == null || array.length == 0) {
            return 0;
        }
        int first = 0;
        int last = array.length - 1;
        int indexMin = 0;
        //2、这里array[first] >= array[last]说明这个数组肯定经过旋转了
        //因为原数组是递增序列，如果没有旋转array[first] <=array[last]
        while (array[first] >= array[last]) {
            //3、指针first始终指向的是前边一个递增子数组序列，last始终指向的是第二个递增子数组序列
            //当last - first == 1说明first指向第一个序列的最后一个元素，last指向第二个序列的第一个元素
            //而且last指向的元素就是整个数组的最小元素
            if (last - first == 1) {
                indexMin = last;
                break;
            }
            indexMin = (first + last) / 2;
            //4、array[indexMin] >= array[first]说明indexMin指向的是第一个序列中的元素
            if (array[indexMin] >= array[first]) {
                first = indexMin;
                //5、array[indexMin] <= array[last]说明indexMin指向的是第二个序列中的元素
            } else if (array[indexMin] <= array[last]) {
                last = indexMin;
            }
        }
        return array[indexMin];
    }
}