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

二分法，时间击败98%

思路： 由于题目所给数组是非递减数组经过一定变化得到的，可以将其看为两部分，每部分都满足非递减的特点，所以也可以使用二分法实现，常用的二分查找是比较array[mid]和target的大小关系进而移动左右边界，此题中没有target，但由于要找最小值，由数组特点可知最小值是两个非递减数组的分界线，所以可以通过比较array[mid]和端点值判断最小值在左半部分还是右半部分，我比较的是右端点，若array[mid]>右端点，说明mid~右端点是非递减数组，最小值必然在左半部分，移动右边界；若小于说明分界线在右半部分，对应最小值必然在右半部分，移动左边界。

特殊情况：

1. 数组未进行旋转，即整个数组都是非递减的，可以用上面的思路解决。
2. 数组全部旋转，即是非递增数组，依然可以用上面的思路解决。
3. 数组端点和array[mid]相等，此时无法确定分界线在左还是在右，此时可以逐渐左移右边界，防止错过答案。

代码：

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int l=0,r=array.length-1;
        while(l<r){
            int mid=l+(r-l)/2;
            while(array[mid]==array[r]&&r>mid){
            //特殊情况3
                r--;
            }
            if(array[mid]>array[r]){
                l=mid+1;
            }else{
                r=mid;
            }
        }
        return array[l];
    }
}