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

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int length = array.length;
        //特殊值处理,此时长度小，可以不用进入循环，提高效率
        if(length == 1){
            return array[0];
        }
        
        //特殊值处理
        if(array[0] < array[length-1]){
            return array[0];
        }
        
        int minValue = array[0];//临时最小值（minValue）
        int min = 0;//二分法，左指针
        int max = length-1;//二分法，右指针
        int mid = (min+max)/2;//二分法，中值
        while(min <= max){
            if(array[mid] == minValue){//中值与临时最小值相等
                int left = mid;
                while(left>min && array[left] == array[left-1]){//往左边寻找第一个与最小值不相等的下标索引
                    left--;
                }
                if(left==min){//左边到中值索引都是相等的，eg:2,2,2,1,2,此时最小值在中值索引右边
                    min = mid + 1;
                }else{//左边到中值索引之间有不相等的，eg:2,0,2,2,2,此时最小值在中值索引左边
                    max = mid - 1;
                }
            }else if(array[mid] > minValue){//中值大于临时最小值（minValue）
                min = mid + 1;
            }else {//中值小于临时最小值（minValue）
                if(array[mid]<array[mid-1]){//如果中值比前一个值小，则该中值是局部最小值，与临时最小值（minValue）比较，可以得到最小值
                    break;//退出循环
                }
                max = mid - 1;//如果中值比前一个值大，此时指针往左移动
            }
            mid = (min+max)/2;
        }
        
        return minValue<array[mid]?minValue:array[mid];//局部最小值（array[mid]）与临时最小值（minValue）比较，可以得到最小值
    }
}