题解 | #二分法求旋转数组最小元素#

function minNumberInRotateArray(rotateArray)
{
    // write code here
    var first = 0;
    var last = rotateArray.length - 1;
//     var NOTE = null;
    if(rotateArray.length == 0){
        return 0;
    }
    while(first != last){
        var mid = first + ((last - first) >> 1);
        if(rotateArray[first] < rotateArray[last]){
            // 数组原本为 非递减数组
            // 旋转之后，应该前面比后面大（前几个放到最后）
            return rotateArray[first]
        }
        if(rotateArray[mid] > rotateArray[last]){
            // 中间那个数比最后那个大，答案在后半部分
            // [3 4 5 1 2]
            first = mid + 1;
        }else if(rotateArray[mid] < rotateArray[last]){
            // 中间那个比后面的小,答案在前半部分
            // [5 1 2 3 4]
            last = mid; 
        }else{
            // 例外情形
            // 原数组[0 1 1 1 1] => [1 0 1 1 1]
            --last
        }
    }
    return rotateArray[first]
}