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) ) );
}
0
投稿猜你喜欢
- 本节为读者讲解如何利用ADO.NET本身的参数对象和存储过程技术防止注入攻击，以达到用户界面输入与原始SQL的分离，使黑客无法拼接SQL语句
作为入门者来说，了解JavaScript中timer的工作方式是很重要的。通常它们的表现行为并不是那么地直观，而这是因为它们都处在一个单一线- 【代码示例】 [code=SQL] DELIMITER $$ DROP FU
- 错误15105，从网上找了一些解决方案，一般都是说文件的权限不足的问题，当然附加的时候必须是有数据库附加权限才可以操作的。解决办法1：给相应
- 大家都知道，数据库的安全性是很重要的，它直接影响到数据库的广泛应用。用户可以采用任意一种方法来保护数据库应用程序，也可以将几种方法结合起来使
- 看了网站LOGO设计规范的思考的第一部分关于logo设计基础，现在接着来谈谈网络LOGO的设计。四、网络LOGO的设计 古代皇家的纹章，有条
- 看了OReilly.JavaScript.The.Definitive.Guide.5th.Edition.Aug.2006里的cookie
- 我们经常会用到表格数据，在做表格的时候，一般都喜欢隔行变色，使表格表现数据的时候非常的清晰。如图，我设计的一个表格表现的样式：在网上找到一个
- 1. 什么是XSLT 大家可能听说过XSL(eXtensible Stylesheet Language)，XSL和我们这里说的XSLT从狭
- 一、逻辑数据库和表的设计数据库的逻辑设计、包括表与表之间的关系是优化关系型数据库性能的核心。一个好的逻辑数据库设计可以为优化数据库和应用程序
- 用科讯CMS“分页显示(专题)文章列表标签”，可以在栏目文章列表下面产生一个页码行。从图可以看出，这段DIV，还需要CSS修饰，但是查看Ht
- 昨天给公司服务器重做了一下系统,遇到Asp附件无法上传,之前服务器上使用好好的,怎么重做了就不正常了,于是一番google，baidu，下面
- 1.安装Apache 在终端中输入下面的命令就可以安装Apache了：sudo yum install httpdsudo的意思是
- 这学期有一门运筹学，讲的两大块儿：线性优化和非线性优化问题。在非线性优化问题这里涉及到拉格朗日乘子法，经常要算一些非常变态的线性方程，于是我
- 在Internet上我们每天都会遇到数不清的表单，也看到其中大部分并没有限制用户多次提交同一个表单。缺乏这种限制有时候会产生某些预料不到的结
- 今天在这里，不以设计师的身份，而从一个普通用户的角度和各位聊聊设计中蕴含的那份情感，关于情感再产品设计中的意义，聊聊设计中的那份源于“心”的
- 古巴比伦王颁布了汉摩拉比法典，刻在黑色的玄武岩，距今已经三千七百多年，你在橱窗前…熟悉吧？没错，这就是周董的爱在西元前歌词。前不久工作不是很
- 内容摘要：在网页制作中，有许多的术语，例如：CSS、HTML、DHTML、XHTML等等。在下面的文章中我们将会用到一些有关于HTML的基本
- 如何一行行地读取文件？这样就可以做到一行行地读出了：dim input(30) ' 定义一个数组,大小
- 不用切图，只要设置基本的 图片及其属性即可！用鼠标右键控制图片翻转！<style>*{ FONT-SIZE: 12px; }se
