PHP有序表查找之二分查找(折半查找)算法示例

yipeiwu_com5年前PHP代码库

本文实例讲述了PHP有序表查找之二分查找(折半查找)算法。分享给大家供大家参考,具体如下:

简介:

二分查找技术,又称为折半查找。它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储。

基本思想:

在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

代码:

<?php
//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function binsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  $middle = intval(($lower + $high) / 2);
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 //返回-1表示查找失败
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = binsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

运行结果:

7
3

总结:

二叉查找的时间复杂度是 O(logn)。不过由于二叉查找的前提条件是需要有序表顺序存储(数组),如果该有序表需要频繁的执行插入或删除操作,维护有序的排序会带来不小的工作量。

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结

希望本文所述对大家PHP程序设计有所帮助。

相关文章

php一些错误处理的方法与技巧总结

1:为什么我得不到变量 我在一网页向另一网页POST数据name,为什么输出$name时却得不到任何值? 在PHP4.2以后的版本中register_global默认为off 若想取得...

php中使用PHPExcel读写excel(xls)文件的方法

本文实例讲述了PHP中使用PHPExcel读写excel(xls)文件的方法,非常实用。分享给大家供大家参考之用。具体方法如下: 很多PHP类库在读取中文的xls、csv文件时会有问题,...

PHP程序员不应该忽略的3点

最近发现很多的PHP程序员,尤其是学习还不是很久的,都不知道PHP的精华所在。Perl当年如何在商界出名?其强大的正则表达式。而PHP呢?他是一门从Unix下发展起来的语言,当然也就继承...

php基础学习之变量的使用

复制代码 代码如下: <?php //引用 $one="test"; two=&$one;//相当于传地址,两个变量指向一个地址 //动态变量 $one="######";...

ThinkPHP Where 条件中常用表达式示例(详解)

Where 条件表达式格式为: $map['字段名'] = array('表达式', '操作条件'); 其中 $map 是一个普通的数组变量,可以根据自己需求而命名。上述格式中...