php二分查找二种实现示例
时间:2023-11-21 00:40:13
php二分查找示例
二分查找常用写法有递归和非递归,在寻找中值的时候,可以用插值法代替求中值法。
当有序数组中的数据均匀递增时,采用插值方法可以将算法复杂度从中值法的lgN减小到lglgN
/**
* 二分查找递归解法
* @param type $subject
* @param type $start
* @param type $end
* @param type $key
* @return boolean
*/
function binarySearch_r($subject, $start, $end, $key)
{
if ( $start >= $end ) return FALSE;
$mid = getMidKey($subject, $start, $end, $key);
if ( $subject[$mid] == $key ) return $mid;
if ( $key > $subject[$mid] ) {
return binarySearch($subject, $mid, $end, $key);
}
if ( $key <= $subject[$mid] ) {
return binarySearch($subject, $start, $mid, $key);
}
}
/**
* 二分查找的非递归算法
* @param type $subject
* @param type $n
* @param type $key
*/
function binarySearch_nr($subject, $n, $key)
{
$low = 0;
$high = $n;
while ( $low <= $high ) {
$mid = getMidKey($subject, $low, $high, $key);
if ( $subject[$mid] == $key ) return $mid;
if ( $subject[$mid] < $key ) {
$low = $mid + 1;
}
if ( $subject[$mid] > $key ) {
$high = $mid - 1;
}
}
}
function getMidKey($subject, $low, $high, $key)
{
/**
* 取中值算法1 取中值 不用 ($low+$high)/2的方式是因为 防止low和high较大时候,产生溢出....
*/
//return round($low + ($high - $low) / 2);
/**
* 经过改进的插值算法求中值,当数值分布均匀情况下,再降低算法复杂度到lglgN
* 取中值算法2
*/
return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) );
}
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
php5.2 Json不能正确处理中文、GB编码的解决方法
在Python中进行自动化单元测试的教程
![](https://img.aspxhome.com/file/2023/1/97711_0s.png)
Django跨域请求CSRF的方法示例
python自动化办公操作PPT的实现
![](https://img.aspxhome.com/file/2023/5/59835_0s.png)
PHP封装的一个支持HTML、JS、PHP重定向的多功能跳转函数
SQL Server 总结复习 (二)
详解Python中while无限迭代循环方法
![](https://img.aspxhome.com/file/2023/4/83694_0s.png)
windows 7安装ORACLE 10g客户端的方法分享
在Python中字典根据多项规则排序的方法
Python 匹配任意字符(包括换行符)的正则表达式写法
Django框架表单操作实例分析
Python3中的json模块使用详解
Python数据可视化编程通过Matplotlib创建散点图代码示例
![](https://img.aspxhome.com/file/2023/0/101160_0s.png)
Python文件操作和异常处理的方法和技巧
详解Python Flask框架的安装及应用
![](https://img.aspxhome.com/file/2023/8/90628_0s.png)
python学习字符串驻留与常量折叠隐藏特性详解
![](https://img.aspxhome.com/file/2023/8/103488_0s.png)
简单了解SQL常用删除语句原理区别
switchery按钮的使用方法
![](https://img.aspxhome.com/file/2023/3/132593_0s.png)
兼容IE,FF的弹出层登陆界面代码
![](https://img.aspxhome.com/file/UploadPic/20081/4/200814122333734s.jpg)