精华内容
下载资源
问答
  • PHP折半查找算法案例详解
    2021-03-25 09:11:13

    这次给大家带来PHP折半查找算法案例详解,使用PHP折半查找的注意事项有哪些,下面就是实战案例,一起来看一下。

    简介:

    二分查找技术,又称为折半查找。它的前提是线性表中的记录必须是关键码有序(通常从小到达有序),线性表必须采用顺序存储。

    基本思想:

    在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功;若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

    代码:<?php

    //二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)

    $i = 0; //存储对比的次数

    //@param 待查找数组

    //@param 待搜索的数字

    function binsearch($arr,$num){

    $count = count($arr);

    $lower = 0;

    $high = $count - 1;

    global $i;

    while($lower <= $high){

    $i ++; //计数器

    if($arr[$lower] == $num){

    return $lower;

    }

    if($arr[$high] == $num){

    return $high;

    }

    $middle = intval(($lower + $high) / 2);

    if($num < $arr[$middle]){

    $high = $middle - 1;

    }else if($num > $arr[$middle]){

    $lower = $middle + 1;

    }else{

    return $middle;

    }

    }

    //返回-1表示查找失败

    return -1;

    }

    $arr = array(0,1,16,24,35,47,59,62,73,88,99);

    $pos = binsearch($arr,62);

    print($pos);

    echo "
    ";

    echo $i;

    运行结果:7

    3

    总结:

    二叉查找的时间复杂度是 O(logn)。不过由于二叉查找的前提条件是需要有序表顺序存储(数组),如果该有序表需要频繁的执行插入或删除操作,维护有序的排序会带来不小的工作量。

    相信看了本文案例你已经掌握了方法,更多精彩请关注php中文网其它相关文章!

    推荐阅读:

    更多相关内容
  • 主要介绍了PHP折半(二分)查找算法,结合实例形式较为详细的分析了php折半(二分)查找算法的概念、原理、实现与使用方法,并附带了一个php折半(二分)查找算法类供大家参考,需要的朋友可以参考下
  • 主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下
  • 这篇文章主要介绍了PHP折半(二分)查找算法,结合实例形式较为详细的分析了php折半(二分)查找算法的概念、原理、实现与使用方法,并附带了一个php折半(二分)查找算法类供大家参考,需要的朋友可以参考下本文实例讲述了...

    这篇文章主要介绍了PHP折半(二分)查找算法,结合实例形式较为详细的分析了php折半(二分)查找算法的概念、原理、实现与使用方法,并附带了一个php折半(二分)查找算法类供大家参考,需要的朋友可以参考下

    本文实例讲述了PHP折半(二分)查找算法。分享给大家供大家参考,具体如下:

    折半查询只适用于已经按照正序或者逆序排序的数组,字符串等;

    算法:

    先取数组的中间位置,无中间位置,则向下取整;

    从中间进行折半,大小判断,进入前半段或者后半段;

    再对前半段或者后半段进行同样的折半查询,

    直到查询到匹配的字符,才停止(本例用break,如果置于函数中,return即可)

    php实现的代码如下:

    $arr = array(1,2,3,4,5,6,7,8,9,10);//数组

    $key = 4;//要查询的关键字

    $low = 0;//开始位的标志

    $high = count($arr);//终止位的标志

    while($low <= $high){//查询开始结束的条件

    $mid = floor(($low + $high)/2);//进行中间位置计算,向下取整

    if($arr[$mid] == $key){//查询成功

    echo $arr[$mid];

    break;//结束本页执行,函数可用return

    }elseif($arr[$mid] > $key){ //查询前半段,把结束标志移到中间位置前一位

    $high = $mid - 1;

    }else{ //查询后半段,把开始位置移到中间位置的后一位

    $low = $mid + 1;

    }

    }

    /*

    运行结果:4

    */

    ?>

    补充:折半(二分)查找算法类:

    /**

    * Description:php实现二分查找算法的类

    * @author wzy

    */

    class binary_search{

    public $arr;

    public $key;

    function __construct($arr,$key){

    //这里初始化的数组已经是有序数组

    $this->arr=$arr;

    $this->key=$key;

    }

    function binarysearch(){

    $start=0;

    $end=count($this->arr)-1;

    while($start<=$end){

    //mid的取值可以为上整数或者下整数

    $mid=ceil(($start+$end)/2);

    //$mid=($start+$end)>>1;

    //$mid=intval(($start+$end)/2);

    if($this->arr[$mid]key){

    $start=$mid+1;

    }else if($this->arr[$mid]>$this->key){

    $end=$mid-1;

    }else{

    return $mid;

    }

    }

    }

    }

    可能大家还会遇到这种情况,数组中的元素有重复数据,需要返回的是重复数据中的第一个元素的位置,例如

    $arr=array(1,2,3,4,5,6,6,6,6,7,8);

    查找6这个元素时返回的位置应该为5,而不是其他(下标从0开始计数),这样需要在返回的mid进行判断,代码如下:

    /**

    * Description:php实现二分查找算法的类

    * @author wzy

    */

    class binary_search{

    public $arr;

    public $key;

    function __construct($arr,$key){

    //这里初始化的数组已经是有序数组

    $this->arr=$arr;

    $this->key=$key;

    }

    function binarysearch(){

    $start=0;

    $end=count($this->arr)-1;

    while($start<=$end){

    //mid的取值可以为上整数或者下整数

    $mid=ceil(($start+$end)/2);

    //$mid=($start+$end)>>1;

    //$mid=intval(($start+$end)/2);

    if($this->arr[$mid]key){

    $start=$mid+1;

    }else if($this->arr[$mid]>$this->key){

    $end=$mid-1;

    }else{

    //返回第一个匹配的元素

    for($i=$mid-1;$i>=0;$i--){

    if($this->arr[$i]==$this->key){

    $mid=$i;

    }else{

    break;

    }

    }

    return $mid;

    }

    }

    }

    }

    您可能感兴趣的文章:

    PHP折半(二分)查找算法实例分析php技巧

    layui框架实现文件上传及TP3.2.3对上传文件进行后台处理操作示例

    Laravel框架实现model层的增删改查操作示例

    展开全文
  • 这篇文章主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下本文实例讲述了PHP实现的折半查找算法。...

    这篇文章主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下

    本文实例讲述了PHP实现的折半查找算法。分享给大家供大家参考,具体如下:

    定义:折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。

    折半查找的基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字,则在中间记录的关键字相等,则查找成功;若给定值小于中间记录的作伴去继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

    实现代码:

    //递归方式

    function bin_recur_search($arr,$val){

    global $time;

    if(count($arr) >= 1){

    $mid = intval(count($arr) / 2);

    $time++;

    if($arr[$mid] == $val){

    return '值为:'.$arr[$mid].'
    查找次数:'.$time.'
    ';

    }elseif($arr[$mid] > $val){

    $arr = array_splice($arr,0,$mid);

    return bin_recur_search($arr, $val);

    }else{

    $arr = array_slice($arr,$mid + 1);

    return bin_recur_search($arr, $val);

    }

    }

    return '未找到'.$val;

    }

    //非递归方式

    function bin_search($arr,$val){

    if(count($arr) >= 1){

    $low = 0;

    $high = count($arr);

    $time = 0;

    while($low <= $high){

    $time++;

    $mid = intval(($low + $high)/2);

    if($val == $arr[$mid]){

    return '索引:'.$mid.'
    值为:'.$arr[$mid].'
    查找次数:'.$time;

    }elseif($val > $arr[$mid]){

    $low = $mid + 1;

    }else{

    $high = $mid - 1;

    }

    }

    }

    return '未找到'.$val;

    }

    $arr = array(1,3,5,7,7,9,25,68,98,145,673,8542);

    echo bin_recur_search($arr, 673);

    echo bin_search($arr, 673);

    ?>

    运行结果:

    值为:673

    查找次数:4

    索引:10

    值为:673

    查找次数:4

    您可能感兴趣的文章:

    展开全文
  • 本文主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下,希望能帮助到大家。定义:折半查找技术,也...

    本文主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下,希望能帮助到大家。

    定义:折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。

    折半查找的基本思想:取中间记录作为比较对象,若给定值与中间记录的关键字,则在中间记录的关键字相等,则查找成功;若给定值小于中间记录的作伴去继续查找;若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。不断重复上述过程,直到查找成功,或所有查找区域无记录,查找失败为止。

    实现代码:

    //递归方式

    function bin_recur_search($arr,$val){

    global $time;

    if(count($arr) >= 1){

    $mid = intval(count($arr) / 2);

    $time++;

    if($arr[$mid] == $val){

    return '值为:'.$arr[$mid].'
    查找次数:'.$time.'
    ';

    }elseif($arr[$mid] > $val){

    $arr = array_splice($arr,0,$mid);

    return bin_recur_search($arr, $val);

    }else{

    $arr = array_slice($arr,$mid + 1);

    return bin_recur_search($arr, $val);

    }

    }

    return '未找到'.$val;

    }

    //非递归方式

    function bin_search($arr,$val){

    if(count($arr) >= 1){

    $low = 0;

    $high = count($arr);

    $time = 0;

    while($low <= $high){

    $time++;

    $mid = intval(($low + $high)/2);

    if($val == $arr[$mid]){

    return '索引:'.$mid.'
    值为:'.$arr[$mid].'
    查找次数:'.$time;

    }elseif($val > $arr[$mid]){

    $low = $mid + 1;

    }else{

    $high = $mid - 1;

    }

    }

    }

    return '未找到'.$val;

    }

    $arr = array(1,3,5,7,7,9,25,68,98,145,673,8542);

    echo bin_recur_search($arr, 673);

    echo bin_search($arr, 673);

    ?>

    运行结果:值为:673

    查找次数:4

    索引:10

    值为:673

    查找次数:4

    相关推荐:

    展开全文
  • //php二分法查找(也叫折半查找)算法/ 数组必须是从小到大的$abs=array(1,12,13,114,115,116,117,118);//z查找数组的最大下标$hight = count($abs) - 1 ;$low =0;$num = 6;//var_dump($abs);//基本思想// 1首先找到...
  • 主要介绍了PHP有序表查找之二分查找(折半查找)算法,简单介绍了二分查找的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下
  • 【优缺点】折半查找法的优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而 查找频繁的有序列表。【算法思想】首先,将表中间位置记录的...
  • 折半查找概念折半查找,又称二分查找。前提是线性表中的记录必须是关键码有序(由小到大或由大到小),线性表必须采用顺序存储。折半查找的基本思想是:在有序表中,取中间值为比较对象,如果给定的值和中间值的关键字...
  • PHP折半查找

    2020-05-12 15:33:54
    折半查找技术,也就是二分查找。它的前提是线性表中的记录必须是关键码有序(通常从大到小有序),线性表必须采用顺序存储。 折半查找的基本思想 取中间记录作为比较对象,若给定值与中间记录的关键字,则在中间...
  • Python实现二分查找法(基于顺序表)class List:elem=[] #存储顺序表元素last=-1 #设置初始为-1SeqList = List() #创建一个顺序表print("欢迎来到我的二分查找(停止输入……Y,继续输入……N),回车开始下一次输入")...
  • 主要介绍了PHP实现的折半查询算法,结合完整实例形式分析了php使用递归与非递归实现折半查询的算法操作步骤与使用方法,需要的朋友可以参考下
  • 递归的折半查找算法

    2021-04-30 02:01:33
    //求中间位置 if (R[mid].key==k) //查找成功返回其逻辑序号mid+1 return mid+1; if (R[mid].key>k) //在R[low..mid-1]中递归查找 BinSearch1(R,low,mid-1,k); else //在R[mid+1..high]中递归查找 BinSearch1(R,mid...
  • 冒泡排序+折半查找法

    2021-11-30 09:43:26
    #include<stdio.h> int main() { int i,j; int arr[10] = {20,51,10,2002,14,102,30,78,98,45} ;//可修改 int l=sizeof(arr)/sizeof(arr[0]) ;... printf("该数组一共有%d个值\n",l);... printf(" %d ",...
  • PHP递归实现折半查找

    2018-09-20 18:13:04
    php  $array = array('6','16','24','36','50','54','72','96','97','103','148','150','153','169','173','194','200','201','202','203','204','215','231','243','245','247','251','258','261','264','2...
  • 查找表:就是同一类型的数据元素构成的数据集合有静态表和动态表本文实现PHP版的二分查找算法【本算法仅用于顺序存储的查找表】/*** Created by PhpStorm.* User: 1655664358@qq.com* Date: 2019/7/01* Time: 11:38*...
  • 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。猜数字游戏大家都应该玩过猜数字的游戏吧?给定一个数字的范围 1...
  • python php 折半查找

    2019-09-30 13:42:44
    二分查找 python实现 #!/usr/bin/python # 输入的列表必须是已经排好序的列表 def binary_search(li, val): left = 0 #定义开始范围 right = len(li)-1 #定义查找结束范围 while left <= right: #如果左边...
  • 折半查找意为从把数组从中间分成两半,找到一个中间值,然后进行判断,首先这个数组一定是从大到小或者从小到大排好序的。 下面的代码里数组是从小到大排序的。 递归形式的: &lt;?php //定义一个从小到大排...
  • 先声明,我在这里写算法,不全是我自己写的代码,是我理解算法后给做得记录。将数列按有序化(递增或递减)排列,查找过程中采用跳跃式方式查找,即先以有序数列的中点位置为比较对象,如果要找的元素值小于该中点元素...
  • 二分查找折半查找法
  • //查找算法public class Search{public int shunXuSearch(int arr[],int key){int i;int m=1;for( i=0;i<=arr.length;i++){System.out.println("程序运算了"+m+"次");m++;if(key==arr[i])break;}re...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,332
精华内容 532
关键字:

php折半查找算法