• 售前

  • 售后

热门帖子
入门百科

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

[复制链接]
小饱1 显示全部楼层 发表于 2021-10-25 20:15:16 |阅读模式 打印 上一主题 下一主题
本文实例讲述了PHP折半(二分)查找算法。分享给各人供各人参考,详细如下:
折半查询只适用于已经按照正序或者逆序排序的数组,字符串等;
算法:
先取数组的中心位置,无中心位置,则向下取整;
从中心进行折半,大小判断,进入前半段或者后半段;
再对前半段或者后半段进行同样的折半查询,
直到查询到匹配的字符,才停止(本例用break,假如置于函数中,return即可)
php实现的代码如下:
  1. <?php
  2. $arr = array(1,2,3,4,5,6,7,8,9,10);//数组
  3. $key = 4;//要查询的关键字
  4. $low = 0;//开始位的标志
  5. $high = count($arr);//终止位的标志
  6. while($low <= $high){//查询开始结束的条件
  7. $mid = floor(($low + $high)/2);//进行中间位置计算,向下取整
  8. if($arr[$mid] == $key){//查询成功
  9. echo $arr[$mid];
  10. break;//结束本页执行,函数可用return
  11. }elseif($arr[$mid] > $key){ //查询前半段,把结束标志移到中间位置前一位
  12. $high = $mid - 1;
  13. }else{ //查询后半段,把开始位置移到中间位置的后一位
  14. $low = $mid + 1;
  15. }
  16. }
  17. /*
  18. 运行结果:4
  19. */
  20. ?>
复制代码
增补:折半(二分)查找算法类:
  1. /**
  2. * Description:php实现二分查找算法的类
  3. * @author wzy
  4. */
  5. class binary_search{
  6.   public $arr;
  7.   public $key;
  8.   function __construct($arr,$key){
  9.     //这里初始化的数组已经是有序数组
  10.     $this->arr=$arr;
  11.     $this->key=$key;
  12.   }
  13.   function binarysearch(){
  14.     $start=0;
  15.     $end=count($this->arr)-1;
  16.     while($start<=$end){
  17.       //mid的取值可以为上整数或者下整数
  18.       $mid=ceil(($start+$end)/2);
  19.       //$mid=($start+$end)>>1;
  20.       //$mid=intval(($start+$end)/2);
  21.       if($this->arr[$mid]<$this->key){
  22.         $start=$mid+1;
  23.       }else if($this->arr[$mid]>$this->key){
  24.         $end=$mid-1;
  25.       }else{
  26.         return $mid;
  27.       }
  28.     }
  29.   }
  30. }
复制代码
大概各人还会碰到这种情况,数组中的元素有重复数据,必要返回的是重复数据中的第一个元素的位置,例如
  1. $arr=array(1,2,3,4,5,6,6,6,6,7,8);
复制代码
查找6这个元素时返回的位置应该为5,而不是其他(下标从0开始计数),这样必要在返回的mid进行判断,代码如下:
  1. /**
  2. * Description:php实现二分查找算法的类
  3. * @author wzy
  4. */
  5. class binary_search{
  6.   public $arr;
  7.   public $key;
  8.   function __construct($arr,$key){
  9.     //这里初始化的数组已经是有序数组
  10.     $this->arr=$arr;
  11.     $this->key=$key;
  12.   }
  13.   function binarysearch(){
  14.     $start=0;
  15.     $end=count($this->arr)-1;
  16.     while($start<=$end){
  17.       //mid的取值可以为上整数或者下整数
  18.       $mid=ceil(($start+$end)/2);
  19.       //$mid=($start+$end)>>1;
  20.       //$mid=intval(($start+$end)/2);
  21.       if($this->arr[$mid]<$this->key){
  22.         $start=$mid+1;
  23.       }else if($this->arr[$mid]>$this->key){
  24.         $end=$mid-1;
  25.       }else{
  26.         //返回第一个匹配的元素
  27.         for($i=$mid-1;$i>=0;$i--){
  28.           if($this->arr[$i]==$this->key){
  29.             $mid=$i;
  30.           }else{
  31.             break;
  32.           }
  33.         }
  34.         return $mid;
  35.       }
  36.     }
  37.   }
  38. }
复制代码
更多关于PHP相干内容感爱好的读者可检察本站专题:《PHP数据布局与算法教程》、《php步调计划算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操纵本领大全》、《PHP常用遍历算法与本领总结》及《PHP数学运算本领总结》
盼望本文所述对各人PHP步调计划有所资助。

帖子地址: 

回复

使用道具 举报

分享
推广
火星云矿 | 预约S19Pro,享500抵1000!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

草根技术分享(草根吧)是全球知名中文IT技术交流平台,创建于2021年,包含原创博客、精品问答、职业培训、技术社区、资源下载等产品服务,提供原创、优质、完整内容的专业IT技术开发社区。
  • 官方手机版

  • 微信公众号

  • 商务合作