PHP实现二分查找算法(代码详解)
发布:smiling 来源: PHP粉丝网 添加日期:2020-04-14 16:31:56 浏览: 评论:0
二分查找又称折半查找,二分查找算法要求数据必须是有序的,以下是php实现二分查找算法的代码。
一:递归方式
- $array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
- $target = 73;
- $low = 0;
- $high = count($array)-1;
- function bin_search($array, $low, $high, $target){
- if ( $low <= $high){
- var_dump($low, $high);echo "\n";
- $mid = intval(($low+$high)/2 );
- if ($array[$mid] == $target){
- return true;
- }elseif ( $target < $array[$mid]){
- return bin_search($array, $low, $mid-1, $target);
- }else{
- return bin_search($array, $mid+ 1, $high, $target);
- }
- }
- return false;
- }
- $find = bin_search($array, $low, $high, $target);
- var_dump($find);
执行结果
- int(0)
- int(25)
- int(13)
- int(25)
- int(20)
- int(25)
- int(20)
- int(21)
- bool(true)
我们看到,经过4次二分查找,查找区间不断折半,最终找到了$target。
二:循环方式
- $array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
- $target = 73;
- function bin_search($array, $target)
- {
- $low = 0;
- $high = count($array)-1;
- $find = false;
- while (true){
- if ($low <= $high){
- var_dump($low, $high);echo "\n";
- $mid = intval(($low + $high)/2);
- if ($array[$mid] == $target){
- $find = true;
- break;
- } elseif ($array[$mid] < $target){
- $low = $mid+1;
- } elseif ($array[$mid] > $target){
- $high = $mid-1;
- }
- } else {
- break;
- }
- }
- return $find;
- }
- $find = bin_search($array, $target);
- var_dump($find);
执行结果
- int(0)
- int(25)
- int(13)
- int(25)
- int(20)
- int(25)
- int(20)
- int(21)
- bool(true)
我们看到,两种方式过程和结果相同。下面我们来测试下针对关联数组的二分查找算法:
- $array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38];
- $target = 19;
- function bin_search($array, $target)
- {
- $low = 0;
- $high = count($array)-1;
- $key_map = array_keys($array);
- $find = false;
- while (true){
- if ($low <= $high){
- var_dump($low, $high);echo "\n";
- $mid = intval(($low + $high)/2);
- if ($array[$key_map[$mid]] == $target){
- $find = true;
- break;
- } elseif ($array[$key_map[$mid]] < $target){
- $low = $mid+1;
- } elseif ($array[$key_map[$mid]] > $target){
- $high = $mid-1;
- }
- } else {
- break;
- }
- //phpfensi.com
- }
- return $find;
- }
- $find = bin_search($array, $target);
- var_dump($find);
执行结果
- int(0)
- int(8)
- int(5)
- int(8)
- bool(true)
两次二分查找,找到了$target,针对关联数组,我们使用了php的array_keys函数获得这个关联有序数组的key,通过key间接比对$target和$array的值。
Tags: PHP查找算法
- 上一篇:PHP学习之浅谈if与switch的使用与区别
- 下一篇:php的数据类型有哪些
相关文章
- ·PHP实现几个排序和查找算法(2020-02-25)
- ·PHP常用的排序和查找算法(2021-06-15)
- ·PHP折半(二分)查找算法实例分析(2021-09-17)
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)