本文实例讲述了PHP折半(二分)查找算法。分享给大家供大家参考,具体如下:
折半查询只适用于已经按照正序或者逆序排序的数组,字符串等;
算法:
先取数组的中间位置,无中间位置,则向下取整;
从中间进行折半,大小判断,进入前半段或者后半段;
再对前半段或者后半段进行同样的折半查询,
直到查询到匹配的字符,才停止(本例用break,如果置于函数中,return即可)
php实现的代码如下:
<"font-size: medium">补充:折半(二分)查找算法类:/** * 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; } } } }更多关于PHP相关内容感兴趣的读者可查看本站专题:《PHP数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《PHP数组(Array)操作技巧大全》、《PHP常用遍历算法与技巧总结》及《PHP数学运算技巧总结》
希望本文所述对大家PHP程序设计有所帮助。
免责声明:本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除!
《魔兽世界》大逃杀!60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容,新游玩模式《强袭风暴》即将于3月21 日在亚服上线,届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕,并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时,他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中,玩家将会进入一个全新的海盗主题大逃杀式限时活动,其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场,作为一个独立于主游戏之外的活动,玩家可以用大逃杀的风格来体验《魔兽世界》,不分职业、不分装备(除了你在赛局中捡到的),光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式,玩家在加入海盗主题的预赛大厅区域前,可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹,《巨龙崛起》和《魔兽世界:巫妖王之怒 经典版》的玩家都可以获得奖励。
更新日志
- 中国武警男声合唱团《辉煌之声1天路》[DTS-WAV分轨]
- 紫薇《旧曲新韵》[320K/MP3][175.29MB]
- 紫薇《旧曲新韵》[FLAC/分轨][550.18MB]
- 周深《反深代词》[先听版][320K/MP3][72.71MB]
- 李佳薇.2024-会发光的【黑籁音乐】【FLAC分轨】
- 后弦.2012-很有爱【天浩盛世】【WAV+CUE】
- 林俊吉.2012-将你惜命命【美华】【WAV+CUE】
- 晓雅《分享》DTS-WAV
- 黑鸭子2008-飞歌[首版][WAV+CUE]
- 黄乙玲1989-水泼落地难收回[日本天龙版][WAV+CUE]
- 周深《反深代词》[先听版][FLAC/分轨][310.97MB]
- 姜育恒1984《什么时候·串起又散落》台湾复刻版[WAV+CUE][1G]
- 那英《如今》引进版[WAV+CUE][1G]
- 蔡幸娟.1991-真的让我爱你吗【飞碟】【WAV+CUE】
- 群星.2024-好团圆电视剧原声带【TME】【FLAC分轨】