PHP二分查找算法的实现方法示例
发布:smiling 来源: PHP粉丝网 添加日期:2018-09-09 13:41:03 浏览: 评论:0
本文实例讲述了PHP二分查找算法的实现方法。分享给大家供大家参考,具体如下:
二分查找法需要数组是一个有序的数组,假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置.
1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比。
2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置。
3. 反之,如果中间值小于我们给定的值,那么说明给定值在中间位置之后,此时需要再次将后一部分的值进行二分,因为在中间值之后,所以我们需要改变的值是开始位置的值,此时开始位置的值应该是我们此时的中间位置,直到我们找到指定值。
4. 或者中间值等于最初的起始位置,或结束位置(此时说明给定值未找到),下面我们来用代码实现~
- //循环实现
- function getValue($num,$arr)
- {
- //查找数组的中间位置
- $length=count($arr);
- $start=0;
- $end=$length;
- $middle=floor(($start+$end)/2);
- //循环判断
- while($start>$end-1)
- {
- if($arr[middle]==$num)
- {
- return middle+1;
- } elseif($arr[middle]<$num)
- {
- //如果当前要查找的值比当前数组的中间值还要打,那么意味着该值在数组的后半段
- //所以起始位置变成当前的middle的值,end位置不变。
- $start=$middle;
- $middle=floor(($start+$end)/2);
- } else{
- //反之
- $end=$middle;
- $middle=floor(($start+$end)/2);
- }
- }
- return false;
- }
- //递归实现
- /*
- * 从数组中获取元素值
- * @param1 int $num,要查找的目标值
- * @param2 array $arr,要查找的数组
- * @param3 int $start,查找的起始位置
- * @param4 int $end,查找的结束位置
- * @return mixed,找到了返回位置,没找到返回false
- */
- function getValue4($num,$arr,$start = 0,$end = 100){
- //采用二分法查找
- $middle = floor(($end + $start) / 2);
- //判断
- if($arr[$middle] == $num){
- //已经找到了,递归的出口
- return $middle + 1;
- }elseif($arr[$middle] < $num){
- //要查找的元素在数组的后半段
- $start = $middle + 1;
- //边界值
- if($start >= $end){
- //没有找到,但是已经超出边界值,递归出口
- return false;
- }
- //调用自己去查找:递归点
- return getValue4($num,$arr,$start,$end); //getValue4($num,$arr,51,100)
- }else{
- //要查找的元素在数组的前半段
- $end = $middle - 1;
- //判断边界值
- if($end < 0)return false;
- //调用自己:递归点
- return getValue4($num,$arr,$start,$end); //getValue4($num,$arr,0,49)
- } //phpfensi.com
- //都没有找到
- return false;
- }
Tags: 示例 算法 方法
- 上一篇:PHP实现无限极分类生成分类树的方法
- 下一篇:PHP清除缓存的几种方法总结
相关文章
- ·php使用ajax示例(2013-12-09)
- ·PHP自动捕捉页面500错误示例(2014-01-19)
- ·PHP验证码实现代码简单示例(2014-08-22)
- ·php验证码程序代码(2014-08-22)
- ·一个完整php验证码实例程序(2014-08-25)
- ·PHP计算身份证校验码示例(2018-05-31)
- ·php利用云片网实现短信验证码功能的示例代码(2018-06-06)
- ·PHP基于双向链表与排序操作实现的会员排名功能示例(2018-06-06)
- ·原生JS实现Ajax通过GET方式与PHP进行交互操作示例(2018-06-11)
- ·php获取客户端IP及URL的方法示例(2018-07-26)
- ·php基于dom实现的图书xml格式数据示例(2018-07-26)
- ·PHP实现多级分类生成树的方法示例(2018-07-31)
- ·PHP基于DOM创建xml文档的方法示例(2018-07-31)
- ·PHP使用DOM和simplexml读取xml文档的方法示例(2018-07-31)
- ·php制作基于xml的RSS订阅源功能示例(2018-07-31)
- ·php实现文件与16进制相互转换的方法示例(2018-08-02)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)