PHP 바이너리 검색의 재귀 및 반복에 대한 자세한 설명

재귀와 반복의 시간 복잡도는 각각 O(N)이고, 반복의 시간 복잡도는 O(logN)입니다. 두 곡선 y=N과 Y=logN에서 알 수 있습니다. 더 나은 것은 O(logN)입니다. 이 기사는 주로 PHP 바이너리 검색의 재귀 및 반복에 대한 자세한 설명을 공유합니다.

다음은 두 가지 코드이며, 완벽한 효율성 테스트를 위한 코드입니다.

<?php  
  
function dichotomyIterationSearch($arr, $n, $v)  
{  
    $left   = 0;  
    $right  = $n - 1;  
    while ($left <= $right) {  
        $middle  = bcp(bcadd($right, $left), 2);  
        if ($arr[$middle] > $v) {  
            $right = $middle - 1;  
        } elseif ($arr[$middle] < $v) {  
            $left  = $middle + 1;  
        } else {  
            return $middle;  
        }  
    }  
    return -1;  
}  
  
  
$arr = [];  
for ($i=0;$i<300000;$i++){  
    $arr[] = $i;  
}  
list($first) = explode(" ",microtime());  
echo dichotomyIterationSearch($arr,count($arr),35387);echo &#39;<br>&#39;;  
list($second) = explode(" ",microtime());  
echo round($second - $first,5)*1000000;  
  
  
function dichotomyRecursionSearch($arr, $low, $high, $v)  
{  
    $middle = bcp(bcadd($low, $high), 2);  
  
    if ($low < $high) {  
        if ($arr[$middle] > $v) {  
            $high = $middle - 1;  
            return dichotomyRecursionSearch($arr, $low, $high, $v);  
        } elseif ($arr[$middle] < $v) {  
            $low = $middle + 1;  
            return dichotomyRecursionSearch($arr, $low, $high, $v);  
        } else {  
            return $middle;  
        }  
    } elseif ($high == $low) {  
        if ($arr[$middle] == $v) {  
            return $middle;  
        } else {  
            return -1;  
        }  
    }  
    return -1;  
}  
  
  
$arr = [];  
for ($i=0;$i<300000;$i++){  
    $arr[] = $i;  
}  
echo "<br>";  
list($first) = explode(" ",microtime());  
echo dichotomyRecursionSearch($arr,0, count($arr),35387);echo &#39;<br>&#39;;  
list($second) = explode(" ",microtime());  
echo round($second - $first, 5)*1000000;

관련 권장 사항:

이진 검색 소개 및 자세한 예

JavaScript가 이진 검색을 사용하여 데이터를 찾는 방법 소개

배열 요소에 대한 이진 검색

위 내용은 PHP 바이너리 검색의 재귀 및 반복에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!