自己动手写了一个二分查找的函数,是用php实现的。相信很多人在面试的时候也碰到过这样的问题。好了,废话太多了,开始吧!
/**
* 二分算法查找
* @param array $array 要查找的数组
* @param int $min_key 数组的最小下标
* @param int $max_key 数组的最大下标
* @param mixed $value 要查找的值
* @return boolean
*/
function bin_search($array,$min_key,$max_key,$value){
if($min_key <= $max_key){
$key = intval(($min_key+$max_key)/2);
if($array[$key] == $value){
return true;
}elseif($value < $array[$key]){
return bin_search($array,$min_key,$key-1,$value);
}else{
return bin_search($array,$key+1,$max_key,$value);
}
}else{
return false;
}
}
//现在我们来测试一下这个函数
$array = array(1,22,23,45,58);
$value = 45;
$min_key = min(array_keys($array));
$max_key = max(array_keys($array));
if(bin_search($array,$min_key,$max_key,$value)){
echo "Search Success!";
}else{
echo "Search Faliure!";
}
这样就实现了二分查找的功能了,是不是很简单呢?
这里涉及到了两个知识点:
首先是二分算法的概念:如下
1、二分查找的先决条件:就是表中结点按关键字有序,且顺序(一维数组)存储.
2、二分法思想:取中,比较
(2.1)求有序表的中间位置mid
(2.2)若r[mid].key == k,则查找成功,若r[mid].key > k,在左子表中继续进行二分查找;若r[mid].key < k,则在右字表中继续进行二分查找
然后就是 递归了,这个大家都比较熟悉,在此就不多说了.
分享到:
相关推荐
主要介绍了php实现的二分查找算法,结合具体实例形式分析了php二分查找算法的实现与使用技巧,涉及php数组判断、遍历、计算等相关操作,需要的朋友可以参考下
主要介绍了PHP二分查找算法,结合实例形式分析了php基于递归与非递归方法实现二分查找的具体操作技巧,需要的朋友可以参考下
主要介绍了PHP二分查找算法的实现方法,简单分析了二分查找算法的原理,并结合具体实例形式给出了php基于循环与递归两种方法实现二分查找的相关操作技巧,需要的朋友可以参考下
本文实例讲述了PHP有序表查找之二分查找(折半查找)算法。分享给大家供大家参考,具体如下: 简介: 二分查找技术,又称为折半查找。它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须...
php二分查找示例 二分查找常用写法有递归和非递归,在寻找中值的时候,可以用插值法代替求中值法。当有序数组中的数据均匀递增时,采用插值方法可以将算法复杂度从中值法的lgN减小到lglgN 复制代码 代码如下:/** * ...
定义:折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。 折半查找的基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字,则在...
本文实例讲述了PHP有序表查找之插值查找算法。分享给大家供大家参考,具体如下: 前言: 在前面我们介绍了二分查找,但是...以上的分析其实就是插值查找的思想,它是二分查找的改进。 基本思想: 根据要查找的关键字ke
主要介绍了PHP基于二分法实现数组查找功能,结合实例形式分析了while循环与递归调用算法实现二分查找功能的相关实现技巧,需要的朋友可以参考下
1个目标文件,JNDI的使用例子,有源代码,可以下载参考,JNDI的使用,初始化Context,它是连接JNDI树的起始点,查找你要的对象,打印找到的对象,关闭Context…… ftp文件传输 2个目标文件,FTP的目标是:(1)提高...
1个目标文件,JNDI的使用例子,有源代码,可以下载参考,JNDI的使用,初始化Context,它是连接JNDI树的起始点,查找你要的对象,打印找到的对象,关闭Context…… ftp文件传输 2个目标文件,FTP的目标是:(1)提高...
JCarder 是一个用来查找多线程应用程序中一些潜在的死锁,通过对 Java 字节码的动态分析来完成死锁分析。 Java的Flash解析、生成器 jActionScript jActionScript 是一个使用了 JavaSWF2 的 Flash 解析器和生成器。...
JCarder 是一个用来查找多线程应用程序中一些潜在的死锁,通过对 Java 字节码的动态分析来完成死锁分析。 Java的Flash解析、生成器 jActionScript jActionScript 是一个使用了 JavaSWF2 的 Flash 解析器和生成器。...
JCarder 是一个用来查找多线程应用程序中一些潜在的死锁,通过对 Java 字节码的动态分析来完成死锁分析。 Java的Flash解析、生成器 jActionScript jActionScript 是一个使用了 JavaSWF2 的 Flash 解析器和生成器。...