So implementieren Sie PHP, um den Mindestwert nach dem Rotieren eines geordneten Arrays (Code) zu finden

Der Inhalt dieses Artikels befasst sich mit der Ermittlung des Mindestwerts (Code) nach dem Rotieren eines geordneten Arrays. Ich hoffe, dass er für Sie hilfreich ist.

Das Verschieben der ersten Elemente eines Arrays an das Ende des Arrays wird als Rotation des Arrays bezeichnet. Gibt eine Drehung eines nicht absteigend sortierten Arrays ein und gibt das kleinste Element des gedrehten Arrays aus. Beispielsweise ist das Array {3,4,5,1,2} eine Rotation von {1,2,3,4,5} und der Mindestwert des Arrays ist 1.

HINWEIS: Alle angegebenen Elemente sind größer als 0. Wenn die Array-Größe 0 ist, geben Sie bitte 0 zurück.

1. Verwenden Sie die Dichotomiemethode, um das kleinste Element im Array zu finden

2. Definieren Sie zwei Zeiger links und rechts, die auf das erste und das letzte Element zeigen Definieren Sie im Array einen mittleren Zeiger in der Mitte

3. Wenn arr[left] kleiner als arr[mid] ist, bewegen Sie den linken Zeiger auf die Mitte, und die Mitte wird neu berechnet 4. Wenn arr[left] größer als arr[mid] ist, bewegen Sie den rechten Zeiger auf die Mitte. Die Mitte wird neu berechnet und der Bereich wird reduziert

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)

Das obige ist der detaillierte Inhalt vonSo implementieren Sie PHP, um den Mindestwert nach dem Rotieren eines geordneten Arrays (Code) zu finden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!