정렬된 배열을 회전한 후 최소값을 찾기 위해 PHP를 구현하는 방법(코드)-PHP 튜토리얼-php.cn

정렬된 배열을 회전한 후 최소값을 찾기 위해 PHP를 구현하는 방법(코드)

不言

풀어 주다： 2023-04-04 08:08:02

원래의

1703명이 탐색했습니다.

이 기사의 내용은 순서가 지정된 배열을 회전시킨 후 PHP에서 최소값(코드)을 찾는 방법에 대한 것입니다. 특정 참조 값이 있으므로 도움이 될 것입니다.

배열의 첫 번째 요소를 배열의 끝으로 이동하는 것을 배열 회전이라고 합니다. 비감소 정렬 배열의 회전을 입력하고 회전된 배열의 가장 작은 요소를 출력합니다. 예를 들어 배열 {3,4,5,1,2}는 {1,2,3,4,5}의 회전이고 배열의 최소값은 1입니다.

참고: 제공된 모든 요소는 0보다 큽니다. 배열 크기가 0인 경우 0을 반환하세요.

1. 이분법을 사용하여 배열에서 가장 작은 요소를 찾습니다.

2. 배열의 첫 번째 요소와 마지막 요소를 가리키는 왼쪽과 오른쪽 두 개의 포인터를 정의하고 중간 포인터를 정의합니다.
3. arr[왼쪽]이 arr[mid]보다 작으면 왼쪽 포인터를 mid로 이동하면 mid가 다시 계산됩니다. 4. arr[왼쪽]이 arr[mid]보다 큰 경우 오른쪽 포인터를 mid로 이동하면 mid가 다시 계산되어 범위가 줄어듭니다

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)

로그인 후 복사

위 내용은 정렬된 배열을 회전한 후 최소값을 찾기 위해 PHP를 구현하는 방법(코드)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!