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

/*
*首先判断首尾是不是最小，这样后面二分判断的时候就不用再考虑这种情况。
*然后就是要考虑相等序列的情况，如果找到最后发现是相等的，就要回头搜索另一个序列，用了一个*partFlag变量来标记那一半是没被搜索过的。
*/
function minNumberInRotateArray(rotateArray)
{
    let array = rotateArray
    
    let partFlag = null;
    
    let left = 0;
    let right = array.length - 1;
    let middle;
    if(array[left]<array[right]){
        return array[left];
    }
    if(array[right]<array[right-1]){
        return array[right];
    }
    while (true) {
        if(right == left){
            return array[right];
        }
        if(right-left==1){
            if(array[left] != array[right]){
                return Math.min(array[left], array[right]);
            }
            if(partFlag==0){
                left = Math.floor((array.length - 1) / 2);
                right = array.length - 1
            }
            else{
                left = 0
                right = Math.floor((array.length - 1) / 2);
            }
        }
        
        middle = Math.floor((left + right) / 2);
        if(array[middle]<array[middle-1]&&array[middle]<array[middle+1]){
            return array[middle];
        }
        
        if (array[middle] >= array[left]) {
            left = middle;
            if(partFlag==null){
                partFlag=1;
            }
        }
        else{
            right = middle;
            if(partFlag==null){
                partFlag=0;
            }
        }
    }
}



module.exports = {
    minNumberInRotateArray : minNumberInRotateArray
};