How to find the minimum value in php after rotating an ordered array (code)

The content of this article is about how to find the minimum value (code) after rotating an ordered array in PHP. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

Moving the first elements of an array to the end of the array is called rotation of the array. Inputs a rotation of a non-decreasingly sorted array and outputs the smallest element of the rotated array. For example, the array {3,4,5,1,2} is a rotation of {1,2,3,4,5}, and the minimum value of the array is 1.

NOTE: All elements given are greater than 0. If the array size is 0, please return 0.

1. Use the dichotomy method to find the smallest element in the array.

2. Define two pointers left and right, pointing to the first element and the last element of the array. , define an intermediate pointer mid

3. If arr[left] is less than arr[mid], then move the left pointer to mid, and mid will be recalculated 4. If arr[left] is greater than arr[mid], then move the right pointer to mid, mid will be recalculated and the range will be reduced

left=0 right=arr.length-1
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
$arr=array(3,4,5,6,1,2);
function minNumberInRotateArray($rotateArray){
        $left=0;//左边指针
        $right=count($rotateArray)-1;//右边指针
        //判断条件，left大于right就一直进行
        while($rotateArray[$left]>=$rotateArray[$right]){
                //left和right已经紧挨着了
                if(($right-$left)==1){
                        $mid=$right;
                        break;
                }   
                //中间点
                $mid=ceil($left+($right-$left)/2);
                //left小于中间点
                if($rotateArray[$left]<$rotateArray[$mid]){
                        //left移动到中间点
                        $left=$mid;
                }else{
                        //right移动到中间点
                        $right=$mid;
                }   
        }   
    
        return $rotateArray[$mid];
}
$min=minNumberInRotateArray($arr);
var_dump($min);//int(1)

The above is the detailed content of How to find the minimum value in php after rotating an ordered array (code). For more information, please follow other related articles on the PHP Chinese website!