关于递归和迭代分别的时间复杂度，递归的时间复杂度是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 '<br>';
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 '<br>';
list($second) = explode(" ",microtime());
echo round($second - $first, 5)*1000000;
相关推荐：
二分法查找介绍及实例详解
javascript如何使用二分法查找数据的方法介绍
二分法查找数组中的元素
以上就是php二分法查找之递归和迭代详解的详细内容。