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

• 题目确实说的不清楚，应该是非递减有序数列，否则只能暴力解法了

• 思路：

  1. 特殊情况：当数组长度小于等于2时，直接返回最后一个数
  2. 本题相当于是一个分段函数，每段都是非单调递增，目标点位于分段处，
  3. 利用二分算法，本题的判断条件可以是：
     • 当array[mid]比两边的数都小，直接返回；
     • 当array[mid]<=array[mid+1],且<=array[length-1],说明位于第二段内，目标点在左侧，right=mid-1
     • 然后就是第三种情况位于第一段内，目标点在右侧，left=mid+1
  4. 判断条件中会引入mid-1和mid+1,就需要分出当 mid=0、mid=array.length-1 两种情况单独判断

• 代码感觉不是很精简，分情况太多

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
      //特殊情况，直接返回
        if(array.length<=2)return array[array.length-1];
        
        int left=0;
        int right=array.length-1;
        int mid=0;
      
      //进入循环，条件与二分算法相同
        while(right>=left){
            mid=left+(right-left)/2;
          
          //当mid=0时
            if(mid==0&&array[1]<array[0]){
                return array[1];
            }else if(mid==0&&array[0]<=array[1]){
                return array[0];
            }
          //当mid=array.length-1时
            if(mid==array.length-1)return array[mid];
          //分三种情况分别判断
            if(array[mid]<array[mid-1]&&array[mid]<=array[mid+1]){
                return array[mid];
            }else if(array[mid]<=array[mid+1]&&array[mid]<=array[array.length-1]){
                right=mid-1;
            }else{
                left=mid+1;
            }
        }
        
        return array[mid];
    }
}