剑指offer（7）：旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减序列的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。

分析：

最直观的思路是直接从头到尾遍历数组，查找最小的元素，时间复杂度为 O(n) 。没有利用旋转数组已经分为了两个排序子序列的特性，还不够高效。

推荐解法：

旋转数组实际上可以划分为两个排序的子数组，前面的子数组都大于或者等于后面子数组的而元素，最小元素刚好是两个子数组的分界线。因此可以用二分查找的思想实现时间复杂度为 O(n) 的查找。

牛客AC代码：

import java.util.ArrayList;
public class Solution {
    public static int minNumberInRotateArray(int [] array) {
        if(array.length == ){
            return ;
        }

        int begin = ;
        int end = array.length-;
        while(array[begin]>=array[end]){
            // 普通查找
            if(end - begin<=)
                return normalFind(array,begin,end);

            int mid = (begin+end)/;
            // 当begin/end/mid位置上的元素相等时，无法判断最小元素位于左边还是右边
            // eg: [1, 0, 1, 1, ] 和 [1, 1, 1, 0, 1]都是[0, 1, 1, 1, 1]的旋转数组
            // 第一种情况最小值0在mid的左边，第二种情况最小值0在mid的右边
            // 只能进行普通查找
            if((array[mid] == array[begin]) && (array[mid] == array[end])){
                return normalFind(array,begin,end);
            }

            if(array[mid]>=array[begin]){//去右边查找
                begin = mid;
            }else if(array[mid]<=array[end]){//去左边找
                end = mid;
            }         
        }
        return array[begin];  // 只能返回begin的值
    }

    // 正常的循环遍历查找
    public static int normalFind(int[] array,int begin,int end){
        if(begin == end){
            return array[begin];
        }

        int min = array[begin];
        for(int i=begin+;i<=end;i++){
            if(array[i]<min){
                min = array[i];
            }
        }
        return min;
    }
           

参考

1. 何海涛，剑指offer名企面试官精讲典型编程题（纪念版），电子工业出版社