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

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        //首先这也是一个有序的数组，有序分为两节
        //并且可以知道，最小值，是旋转部分的头
        //可以理解为往中间找最小值
        //比较：第左边的值还要小；比右边的值还要大
        int left = 0;
        int right = array.length-1;
        while (left < right) {
            //mid的值可能等于left
            int mid = (left + right) / 2;
            if (array[mid] < array[left]) {
                //说明最小值在mid前面
                right = mid;
            } else if (array[mid] > array[right]){
                //说明最小值在mid后面
                left = mid + 1;
            }else{
                //大于等于left并且小于等于right
                //当存在left==mid，不能移动左指针
                //可以移动右指针的原因是，右指针的数字只能大于等于mid
                right--;

            }
        }
        return array[left];
    }
}

首先要分析，二分法只能用于有序数组。这其实是一个两节的有序数组。比较mid和left，比left小说明在mid前面，比right大，说明在mid后面。然后要注意在此之间的情况，就是移动右指针即可，不要动左指针，因为会存在mid=left的情况，这时候mid要比right小，可以right--