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

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function minNumberInRotateArray( $nums )
{
    return binary($nums, 0, count($nums)-1);
}

function binary($nums, $lower, $higher){
    if($lower >= $higher){
        return $nums[$lower];
    }
    $mid = intval(($lower+$higher)/2);
    if($nums[$mid] > $nums[$higher]){
        return binary($nums, $mid+1, $higher);
    }elseif($nums[$mid] < $nums[$higher]){
        return binary($nums, $lower, $mid);
    }else{
        return binary($nums, $lower, $higher-1);
    }
}

看到有序数组就想到二分法。如果mid > higher，则证明旋转点在mid+1~higher这个范围内；如果mid < higher, 则证明旋转点在lower~mid这个范围内；如果mid == higher，则无法判断旋转点在哪里，只能确定不是最后一个，所以范围是lower~higher-1