[PHP]算法-旋转数组的最小值的PHP实现

admin

[PHP] 纯文本查看 复制代码

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

1.可以看成是二分查找法，查找最小的元素
2.{3,4,5,1,2} 可以看成{3,4,5} {1,2}，left和right两个指针分别指向第一个和最后一个
3.mid=left+(right-left)/2 如果arr[left] <= arr[mid]  那么 left指针移到mid处，left=mid
    如果arr[left] > arr[mid]那中间元素必定是在右半区，right指针移到mid处  right=mid
4.终止条件是right-left=1 mid=right
5.

minNumberInRotateArray(arr)
    while arr[left]>arr[right]
        if (right-left)==1
            mid=right
            break
        mid=left+(right-left)/2
        if arr[left]<=arr[mid]
            left=mid
        else
            right=mid
    return arr[mid]

[PHP] 纯文本查看 复制代码

function minNumberInRotateArray($arr)
{
        $left=0;
        $size=count($arr);
        $right=$size-1;
        $mid=$left+intval(($right-$left)/2);
        while($arr[$left]>=$arr[$right]){
                if(($right-$left)==1){
                        $mid=$right;
                        break;
                }  
                $mid=$left+intval(($right-$left)/2);
                if($arr[$left]<=$arr[$mid]){
                        $left=$mid;
                }else{
                        $right=$mid;
                }  
        }  
        return $arr[$mid];
}
 
$arr=array(3,4,5,1,2);
$m=minNumberInRotateArray($arr);
var_dump($m);