题解 | #旋转数组的最小数字#

题目（Java题解）

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

示例

input:
    [3,4,5,1,2]
output:    
    1

解题思路

首先明确题目后不难快速得出一个Brute Force的方法，一个O(N)的算法怎么看都不是很糟糕，但是面试官显然想看到的不是这么简单的方法，因此可以考虑通过二叉搜索法实现，现在考虑特殊情况递增数组的旋转，[3,4,5,6,7,8,9,1,2]。维护两个指针left=0，right=8。首先找到mid=4，nums[mid]=7 > nums[right],显然目标值不会在mid的左侧，因此left更新为mid，如果nums[mid]<nums[right]，说明最小值在mid或者mid左边，此时更新right为mid，最后left和right相邻的时候，从left到right必然时非递增的。即此时right对应的值为目标值。
left=4,right=8,mid=6,nums[mid]=9
left=6,right=8,mid=7,nums[mid]=1
left=6,right=7,nums[left]>nums[right]
返回nums[right];
考虑一般情况，即为非递减数组，如果存在[1，1，1，1，1，2，1，1，1]，此时mid为4，nums[mid]=1，不能判断属于左侧还是右侧，对于这种情况应该通过直接遍历的方式实现。
同理还是要询问面试官是否需要处理特殊情况。

时间复杂度：
基于比较的时间复杂度O(lgN)，特殊情况的时间复杂度为O(N)

实例代码

Binary

public class Solution {
   public int minNumberInRotateArray(int [] array) {
       if(array == null || array.length == 0){
           return -1;
       }
       int left = 0;
       int right = array.length - 1;
       while(right - left != 1){
           int mid = left + (right - left) / 2;
           if(array[mid] == array[right]){
               return processWithBrute(array);
           }else if(array[mid] > array[right]){
               left = mid;
           }else{
               right = mid;
           }
       }
       return array[right];
   }
    public int processWithBrute(int[] array){
        int min = array[0];
        for(int i = 1; i < array.length; i++){
            if(array[i] < min){
                min = array[i];
            }
        }
        return min;
    }
}

测试用例

1. 功能性测试，一个升序排序数组的翻转
2. 边界值测试，只包含一个数字的数组
3. 特殊输入测试，输入为空