PHP基于二分法实现数组查找功能示例【循环与递归算法】

本文实例讲述了PHP基于二分法实现数组查找功能。分享给大家供大家参考,具体如下:

二分法。分别使用while循环的方法和递归调用的方法。

<?php
// 二分法的使用数组必须是有序的,或升序,或降序
$arr = array(
  1, 3, 5, 7, 9, 13
);
// 递归调用(相比较好理解
function bsearch_r($v, $arr, $low, $high){
  if ($low > $high) {// 先判断结束条件
    return -1;
  }
  $i = intval(($high + $low)/2);
  if ($arr[$i] > $v){
    return bsearch_r($v, $arr, $low, $i-1);// 递归
  } else if ($arr[$i] < $v){
    return bsearch_r($v, $arr, $i+1, $high);
  } else {
    return $i;
  }
}
echo bsearch_r(1, $arr, 0, count($arr)-1);// 0
echo '<hr/>';
echo bsearch_r(14, $arr, 0, count($arr)-1);// -1
echo '<hr/>';
// while循环
function bsearch($v, $arr){
  $low = 0;
  $high = count($arr)-1;// 使用下标,注意减去1
  // 注意凡是使用到while的时候,一定要防备无限循环的时候,注意终止循环的判断。
  while($low <= $high){// 比如$low<=$high,这个等于号必须有。
    $i = intval(($high + $low)/2);
    if ($arr[$i] > $v){
      $high = $i-1;
    } else if ($arr[$i] < $v){
      $low = $i+1;
    } else {
      return $i;
    }
  }
  return -1;// 找不到的时候返回-1
}
echo bsearch(13, $arr);// 5
echo '<hr/>';
echo bsearch(14, $arr);// -1

运行结果:

更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》

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

(0)

相关推荐

  • php二分法在IP地址查询中的应用

    数据库大概存储几十万条IP记录,记录集如下: +----------+----------+------------+---------+---------+--------+--------+  | ip_begin | ip_end   | country_id | prov_id | city_id | isp_id | netbar |  +----------+----------+------------+---------+---------+--------+--------+ 

  • 深入理解PHP几个算法:PHP冒泡、PHP二分法、PHP求素数、PHP乘法表

    PHP几个算法整理 涉及到以下几个示例.PHP冒泡PHP二分法PHP求素数PHP乘法表 PHP冒泡法 示例 复制代码 代码如下: //PHP冒泡  从小到大function maopao(&$arr){  if(!empty($arr))  {    for($i=0;$i<count($arr);$i++)      {        if($arr[$i]>$arr[$j])        {          //开始交换          $temp = $arr[$i];  

  • 解析php二分法查找数组是否包含某一元素

    二分法查找数组是否包含某一元素,兼容正反序,代码实现: 复制代码 代码如下: <?php $searchValue = (int)$_GET['key']; function search(array $array, $value) {     $max = count($array)-1;     $min = 0;     $isAscSort = $array[$min] < $array[$max]; while (TRUE) {         $sum = $min+$max;  

  • 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 /** * 查找 * **/ // 顺序查找 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字符串逆序排列实现方法小结【strrev函数,二分法,循环法,递归法】

    本文实例总结了PHP字符串逆序排列实现方法.分享给大家供大家参考,具体如下: 关于字符串的逆序排列,最简单的使用PHP函数strrev()的测试代码如下: header('Content-type: text/html; charset=utf-8'); $str = implode('', range(9, 0)); print '< p><strong>Before reversed: </strong>'.$str.'< /p>'; print '&l

  • php 数组二分法查找函数代码

    复制代码 代码如下: <?php //search函数 其中$array为数组,$k为要找的值,$low为查找范围的最小键值,$high为查找范围的最大键值 function search($array, $k, $low=0, $high=0) { if(count($array)!=0 and $high == 0) //判断是否为第一次调用 { $high = count($array); } if($low <= $high) //如果还存在剩余的数组元素 { $mid = intva

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

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

  • PHP基于二分法实现数组查找功能示例【循环与递归算法】

    本文实例讲述了PHP基于二分法实现数组查找功能.分享给大家供大家参考,具体如下: 二分法.分别使用while循环的方法和递归调用的方法. <?php // 二分法的使用数组必须是有序的,或升序,或降序 $arr = array( 1, 3, 5, 7, 9, 13 ); // 递归调用(相比较好理解 function bsearch_r($v, $arr, $low, $high){ if ($low > $high) {// 先判断结束条件 return -1; } $i = intval(

  • JS实现的Object数组去重功能示例【数组成员为Object对象】

    本文实例讲述了JS实现的Object数组去重功能.分享给大家供大家参考,具体如下: 目标:实现成员为 Object 的数组的去重. 注意,这里的数组成员为 Object,而不是数值或者字符串. 调用方法: arr = distinct_arr_element(arr); 函数: /* * 在数组中去除重复项() */ var distinct_arr_element = function( arr ){ if( !arr ) return null ; var resultArr = []; $

  • asp.net基于Calendar实现blog日历功能示例

    本文实例讲述了asp.net基于Calendar实现blog日历功能.分享给大家供大家参考,具体如下: 怎样用.net的Calendar控件来实现blog中站点日历的效果呢,我们知道站点日历最重要的功能就是,显现在哪天blog主人写了日志,点击日期,你将进入所选日期的日志列表, 首先,我们知道.net中的服务器控件是会进行Postback的,Calendar控件中的第一天在点击时,就会进行一次postback我们要做的就是改变它默认的链接,使它不触发postback事件,其次,就是要知道哪一天有

  • PHP实现二维数组去重功能示例

    本文实例讲述了PHP实现二维数组去重功能.分享给大家供大家参考,具体如下: php中二维数组去重操作.例如从数据库中查询出的记录,根据某个键做去重操操作 代码如下: /** * 删除二维数组中相同项的数据,(一般用于数据库查询结果中相同记录的去重操作) * * @param array $_2d_array 二维数组,类似: * $tmpArr = array( * array('id' => 1, 'value' => '15046f5de5bb708e'), * array('id' =&

  • Python基于递归实现电话号码映射功能示例

    本文实例讲述了Python基于递归实现电话号码映射功能.分享给大家供大家参考,具体如下: 问题 电话按键上面的每个数字都对应着几个字母,如果按下一个数字键代表输入一个字母,那么输入一个数字组成的字符串,它所产生的所有的可能的字母串是什么,有多少种 思路: 这个是一个递归的问题 下面是具体的实现,为了更清晰看懂递归调用的过程,这里打印出来了每一次递归的过程: #!usr/bin/env python #encoding:utf-8 ''''' __Author__:沂水寒城 功能:电话号码映射 '

  • PHP基于cookie实现统计在线人数功能示例

    本文实例讲述了PHP基于cookie实现统计在线人数功能.分享给大家供大家参考,具体如下: online.php文件: <?php /* @ PHP 在线人数统计程序 Copyright (c) www.vgot.cn by Pader 1:25 2009年1月7日 Homepage:http://www.vgot.cn QQ: 270075658 How to use it: <script src="online.php"></script> note

  • PHP自定义函数实现数组比较功能示例

    本文实例讲述了PHP自定义函数实现数组比较功能.分享给大家供大家参考,具体如下: <?php //数组使用标准比较运算符这样比较的 function standard_array_compare($op1,$op2) { if(count($op1) < count($op2)) { return -1; //$op1 < $op2 } else if(count($op1) > count($op1)) { return 1; //$op1 > op2 } foreach

  • Python+Socket实现基于UDP协议的局域网广播功能示例

    本文实例讲述了Python+Socket实现基于UDP协议的局域网广播功能.分享给大家供大家参考,具体如下: 服务器端: # udp_gb_server.py '''服务端(UDP协议局域网广播)''' import socket s = socket.socket(socket.AF_INET, socket.SOCK_DGRAM) s.setsockopt(socket.SOL_SOCKET, socket.SO_BROADCAST, 1) PORT = 1060 network = '<b

  • php基于SQLite实现的分页功能示例

    本文实例讲述了php基于SQLite实现的分页功能.分享给大家供大家参考,具体如下: 这里操作数据库文件使用的是前面文章<PHP基于PDO实现的SQLite操作类[包含增删改查及事务等操作]>中的SQLite数据库操作类.废话不说,直接上代码: <meta charset='utf-8'> <?php class SqlitePage{ public function __construct() { $this->table_name=''; $this->tj=

  • Python实现字符串与数组相互转换功能示例

    本文实例讲述了Python实现字符串与数组相互转换功能.分享给大家供大家参考,具体如下: 字符串转数组 str = '1,2,3' arr = str.split(',') print a 运行结果: 数组转字符串 #方法1 arr = ['a','b'] str1 = ','.join(arr) print str1 #方法2 arr = [1,2,3] #str = ','.join(str(i) for i in arr)#此处str命名与str函数冲突! str2 = ','.join(

随机推荐