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

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param rotateArray int整型一维数组 
 * @return int整型
 */
function minNumberInRotateArray( $rotateArray )
{
    // write code here
    $len = count($rotateArray);
    $start = 0;
    $end = $len -1;
    while ($start <= $end) {
        $mid = ($start + $end) >> 1;
        if ($rotateArray[$mid] > $rotateArray[$end]) {
            $start = $mid + 1;
        } elseif ($rotateArray[$mid] == $rotateArray[$end]) {
            $end--;
        } else {
            $end = $mid;
        }
    }
    return $rotateArray[$start];
}

php实现了排行第二位的大神的思路，自己总结一下思路方便记忆：首先确定的是，数组可分为两个有序的数组，最小的肯定在后半段的数组里，第一步肯定是先找这个后半段数组，用mid去和end比较，如果mid大，那么确定mid不在后半段数组里，如果mid和high相等，那么找high前面的数来做判断，目的是为了让mid能够移动， mid移动到某个值，发现小于end了，表明这个时候，mid已经在后半段数组里了，那么只需要在后半段数组的mid之前的（包含mid）里找最小的就行。