二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x2d056a598f145abd4ec9a4d1c4cfbe05a[n/2],则只要在数组a的右半部搜索x.
下面是实例代码
// 递归二分查找 $arr = [1,2,3,4,11,12,124,1245]; function bin_recur_find($arr, $beg, $end, $v) { if ($beg <= $end) { $idx = floor(($beg + $end)/2); if ($v == $arr[$idx]) { return $idx; } else { if ($v < $arr[$idx]) { return bin_recur_find($arr, $beg, $idx - 1, $v); } else { return bin_recur_find($arr, $idx + 1, $end, $v); } } } return -1; } // 非递归二分查找 function bin_find($arr, $v) { $beg = 0; $end = count($arr) - 1; while ($beg <= $end) { $idx = floor(($beg + $end)/2); if ($v == $arr[$idx]) { return $idx; } else { if ($v < $arr[$idx]) { $end = $idx - 1; } else { $beg = $idx + 1; } } } return -1; } echo bin_recur_find($arr, 0, count($arr) - 1, 100) . "\n"; echo bin_find($arr, 100) . "\n";
以上是php 递归与非递归实现的二分查找实例代码的详细内容。更多信息请关注PHP中文网其他相关文章!