PHP二分查找算法示例【递归与非递归方法】

本文实例讲述了PHP二分查找算法。分享给大家供大家参考，具体如下：

binarySearch

二分查找采用的方法比较容易理解，以数组为例:

① 先取数组中间的值floor((low+top)/2),

② 然后通过与所需查找的数字进行比较，若比中间值大，则将首值替换为中间位置下一个位置，继续第一步的操作；若比中间值小，则将尾值替换为中间位置上一个位置，继续第一步操作

③ 重复第二步操作直至找出目标数字

比如从1，3，9，23，54 中查找数字23，

首位置为0， 尾位置为4，中间位置就为2 值为9，比23小，则首位置更新为2+1即3；那么接下来中间位置就为（3+4）/2=3，值为23，比较相等即找到

//  非递归算法：
//  $target是要查找的目标 $arr是已经排序好的数组
function binary(&$arr,$low,$top,$target){
    while($low <= $top){
//由于php取商是有小数的，所以向下取整，不过也可不加，数组也会取整
      $mid = floor(($low+$top)/2);
      echo $mid."<br>";
      if($arr[$mid]==$target){
        return $arr[$mid];
      }elseif($arr[$mid]<$target){
        $low = $mid+1;
      }else{
        $top = $mid-1;
      }
    }
    return -1;
}

//  递归算法：
function binaryRecursive(&$arr,$low,$top,$target){
    if($low<=$top){
      $mid = floor(($low+$top)/2);
      if($mid==$target){
        return $arr[$mid];
      }elseif($arr[$mid]<$target){
        return binaryRecursive($arr,$mid+1,$top,$target);
      }else{
        return binaryRecursive($arr,$low,$top-1,$target);
      }
    }else{
      return -1;
    }
}

更多关于PHP相关内容感兴趣的读者可查看本站专题：《php查找技巧与方法总结》、《PHP数据结构与算法教程》、《php程序设计算法总结》、《php加密方法总结》、《PHP编码与转码操作技巧汇总》、《php面向对象程序设计入门教程》、《PHP数学运算技巧总结》、《PHP数组(Array)操作技巧大全》、《php字符串(string)用法总结》、《php正则表达式用法总结》、及《php常见数据库操作技巧汇总》

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

赞 (0)

相关推荐

  • 最新用php获取谷歌PR值算法，附上php查询PR值代码示例

    复制代码 代码如下: /* *功能:对URL进行编码 *参数说明:$web_url 网站URL,不包含"http://",例如jb51.net */ function HashURL($url){ $SEED = "Mining PageRank is AGAINST GOOGLE'S TERMS OF SERVICE. Yes, I'm talking to you, scammer."; $Result = 0x01020345; for ($i=0; $i&l

  • PHP实现的折半查询算法示例

    PHP实现的折半查询算法示例

    本文实例讲述了PHP实现的折半查询算法.分享给大家供大家参考,具体如下: 什么是折半查询算法?具体文字描述自己百度.直接上代码: <?php header("Content-type: text/html; charset=utf-8"); /* 折半查询算法--不用递归 */ function qSort($data = array(), $x = 0){ $startIndex = 0; // 开始索引 $endIndex = count($data) - 1; // 结束索

  • php实现的二分查找算法示例

    本文实例讲述了php实现的二分查找算法.分享给大家供大家参考,具体如下: <?php $arr = array(4,58,11,34,88,45,32,54,63,78); function binary($arr,$bnum) { if(is_array($arr) && count($arr) > 0) { sort($arr); $start = 0; $end = count($arr)-1; $mid = -1; while($start <= $end) {

  • PHP二分查找算法的实现方法示例

    本文实例讲述了PHP二分查找算法的实现方法.分享给大家供大家参考,具体如下: 二分查找法需要数组是一个有序的数组 假设我们的数组是一个递增的数组,首先我们需要找到数组的中间位置. 1. 要知道中间位置就需要知道起始位置和结束位置,然后取出中间位置的值来和我们的值做对比. 2. 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置. 3. 反之,如果中间值小于我们给定的值,那么说明给定值

  • 使用PHP实现二分查找算法代码分享

    第一种方法: [二分查找要求]:1.必须采用顺序存储结构 2.必须按关键字大小有序排列. [优缺点]折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表. [算法思想]首先,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表. 复制代码 代码如下: <?

  • php数据结构与算法(PHP描述) 查找与二分法查找

    复制代码 代码如下: <?php /** * 查找 * **/ // 顺序查找 function normal_search($arrData,$val) { $len = count($arrData); if($len == 0) return -1; for($i = 0;$i < $len; $i++ ) { echo "find No.",$i + 1," value = ",$arrData[$i]," is = ",$v

  • php中二分法查找算法实例分析

    本文实例讲述了php中二分法查找算法实现方法.分享给大家供大家参考,具体如下: 二分法查找在高级点的开发可能会用到了,当然在大公司找工作时都会有面试题是这种了,下面我们来看一篇关于二分法查找在php中实现方法,具体的细节如下所示. 二分法(dichotomie) 即一分为二的方法,设[a,b]为R的闭区间,逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的中点

  • PHP常用的排序和查找算法

    本文汇总了常见的php排序算法和查找,在进行算法设计的时候有不错的借鉴价值.现分享给大家供参考之用.具体如下: <?php /** * PHP最常用的四个排序方法及二种查找方法 * 下面的排序方法全部都通过测试 * auther : soulence * date : 2015/06/20 */ //PHP冒泡排序法 function bubbleSort(&$arr){ //这是一个中间变量 $temp=0; //我们要把数组,从小到大排序 //外层循环 $flag=false;//这个优

  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解

    数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组 复制代码 代码如下: //冒泡排序(数组排序)function bubble_sort($array) {$count = count($array);if ($count <= 0)return false;for($i=0; $i<$count; $i++){for($j=$count-1; $j>$i; $j–){if ($array[$j] < $array[$j-1]){$tmp =

  • python二分查找算法的递归实现方法

    本文实例讲述了python二分查找算法的递归实现方法.分享给大家供大家参考,具体如下: 这里先提供一段二分查找的代码: def binarySearch(alist, item): first = 0 last = len(alist)-1 found = False while first<=last and not found: midpoint = (first + last)//2 if alist[midpoint] == item: found = True else: if ite

  • PHP二分查找算法示例【递归与非递归方法】

    本文实例讲述了PHP二分查找算法.分享给大家供大家参考,具体如下: binarySearch 二分查找采用的方法比较容易理解,以数组为例: ① 先取数组中间的值floor((low+top)/2), ② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作:若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作 ③ 重复第二步操作直至找出目标数字 比如从1,3,9,23,54 中查找数字23, 首位置为0, 尾位置为4,中间位置就为2 值为9

  • C语言快速排序与二分查找算法示例

    本文实例讲述了C语言二分排序与查找算法.分享给大家供大家参考,具体如下: 题目:首先产生随机数,再进行快速排序,再进行二分查找. 实现代码: #include <stdio.h> #include <stdlib.h> #include <time.h> void quiksort(int a[],int low,int high) { int i = low; int j = high; int temp = a[i]; if( low < high) { wh

  • PHP有序表查找之插值查找算法示例

    本文实例讲述了PHP有序表查找之插值查找算法.分享给大家供大家参考,具体如下: 前言: 在前面我们介绍了二分查找,但是我们考虑一下,为什么一定要折半呢?而不是折四分之一或者更多? 打个比方,在英文词典里查找"apple",你下意识里翻开词典是翻前面的书页还是后面的书页呢?如果再查"zoo",你又会怎么查?显然你不会从词典中间开始查起,而是有一定目的地往前或往后翻. 同样,比如要在取值范围在 0 ~ 10000 之间的100个元素从小到大均匀分布的数组中查找5,我们自

  • 二分查找算法在C/C++程序中的应用示例

    二分查找算法的思想很简单,<编程珠玑>中的描述: 在一个包含t的数组内,二分查找通过对范围的跟综来解决问题.开始时,范围就是整个数组.通过将范围中间的元素与t比较并丢弃一半范围,范围就被缩小.这个过程一直持续,直到在t被发现,或者那个能够包含t的范围已成为空.         Donald Knuth在他的<Sorting and Searching>一书中指出,尽管第一个二分查找算法早在1946年就被发表,但第一个没有bug的二分查找算法却是在12年后才被发表出来.其中常见的一个

  • Java二分查找算法实现代码实例

    这篇文章主要介绍了Java二分查找算法实现代码实例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 二分查找: 两种方式: 非递归方式和递归方式 主要思路: 对于已排序的数组(先假定是从小到大排序), 先定义两个"指针", 一个"指向"首元素low, 一个"指向"末尾元素high. 然后, 开始折半比较, 即让要查找的数与数组中间的元素(索引为 low+high/2)比较. 若要查找的数比中间数小

  • Python递归函数 二分查找算法实现解析

    Python递归函数 二分查找算法实现解析

    一.初始递归 递归函数:在一个函数里在调用这个函数本身. 递归的最大深度:998 正如你们刚刚看到的,递归函数如果不受到外力的阻止会一直执行下去.但是我们之前已经说过关于函数调用的问题,每一次函数调用都会产生一个属于它自己的名称空间,如果一直调用下去,就会造成名称空间占用太多内存的问题,于是python为了杜绝此类现象,强制的将递归层数控制在了997(只要997!你买不了吃亏,买不了上当...). 拿什么来证明这个"998理论"呢?这里我们可以做一个实验: def foo(n): pr

  • Java实现二分查找算法实例分析

    本文实例讲述了Java实现二分查找算法.分享给大家供大家参考.具体如下: 1. 前提:二分查找的前提是需要查找的数组必须是已排序的,我们这里的实现默认为升序 2. 原理:将数组分为三部分,依次是中值(所谓的中值就是数组中间位置的那个值)前,中值,中值后:将要查找的值和数组的中值进行比较,若小于中值则在中值前面找,若大于中值则在中值后面找,等于中值时直接返回.然后依次是一个递归过程,将前半部分或者后半部分继续分解为三部分.可能描述得不是很清楚,若是不理解可以去网上找.从描述上就可以看出这个算法适合

随机推荐