Detailed explanation of recursion and iteration of PHP binary search

Regarding the time complexity of recursion and iteration, the time complexity of recursion is O(N), while the time complexity of iteration is O(logN). There are two curves: y=N and Y=logN. We know that O(logN) must be better. This article mainly shares with you the detailed explanation of recursion and iteration of PHP binary search. I hope it can help you.

The following are two pieces of code, and the code for fool-proof efficiency testing.

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

Related recommendations:

Introduction to binary search and detailed examples

Introduction to how JavaScript uses binary search to find data

Binary search for elements in an array

The above is the detailed content of Detailed explanation of recursion and iteration of PHP binary search. For more information, please follow other related articles on the PHP Chinese website!