Explication détaillée de la récursivité et de l'itération de la recherche binaire PHP

Concernant la complexité temporelle de la récursion et de l'itération, la complexité temporelle de la récursion est O(N), tandis que la complexité temporelle de l'itération est O(logN). Il existe deux courbes : y=N et Y=logN. Nous savons que O(logN) doit être meilleur. Cet article partage principalement avec vous l'explication détaillée de la récursivité et de l'itération de la recherche binaire PHP. J'espère qu'il pourra vous aider.

Voici deux morceaux de code, ainsi que le code pour des tests d'efficacité infaillibles.

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

Recommandations associées :

Introduction à la recherche binaire et exemples détaillés

Introduction à la façon dont JavaScript utilise la recherche binaire pour trouver des données

Recherche binaire d'éléments dans un tableau

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!