PHP折半(二分)查找算法实例分析
发布:smiling 来源: PHP粉丝网 添加日期:2021-09-17 10:25:21 浏览: 评论:0
这篇文章主要介绍了PHP折半(二分)查找算法,结合实例形式较为详细的分析了php折半(二分)查找算法的概念、原理、实现与使用方法,并附带了一个php折半(二分)查找算法类供大家参考,需要的朋友可以参考下。
本文实例讲述了PHP折半(二分)查找算法,分享给大家供大家参考,具体如下:
折半查询只适用于已经按照正序或者逆序排序的数组,字符串等;
算法:
先取数组的中间位置,无中间位置,则向下取整;
从中间进行折半,大小判断,进入前半段或者后半段;
再对前半段或者后半段进行同样的折半查询,直到查询到匹配的字符,才停止(本例用break,如果置于函数中,return即可)
php实现的代码如下:
- <?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]<$this->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]<$this->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;
- }
- }
- }
- }
Tags: PHP折半 PHP查找算法
相关文章
- ·PHP实现的折半查找算法示例(2021-08-23)
- ·PHP实现几个排序和查找算法(2020-02-25)
- ·PHP实现二分查找算法(代码详解)(2020-04-14)
- ·PHP常用的排序和查找算法(2021-06-15)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)