Detaillierte Erläuterung der Rekursion und Iteration der PHP-Binärsuche

In Bezug auf die zeitliche Komplexität von Rekursion und Iteration beträgt die zeitliche Komplexität der Rekursion O(N), während die zeitliche Komplexität der Iteration O(logN) ist. Es gibt zwei Kurven: y=N und Y=logN Wir wissen, dass O(logN) besser sein muss. Dieser Artikel teilt Ihnen hauptsächlich die detaillierte Erklärung der Rekursion und Iteration der PHP-Binärsuche mit.

Das Folgende sind zwei Codeteile und der Code für narrensichere Effizienztests.

<?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;

Verwandte Empfehlungen:

Einführung in die binäre Suche und detaillierte Beispiele

Einführung, wie JavaScript die binäre Suche zum Suchen von Daten verwendet

Binäre Suche nach Elementen in einem Array

Das obige ist der detaillierte Inhalt vonDetaillierte Erläuterung der Rekursion und Iteration der PHP-Binärsuche. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!