这篇文章主要介绍了PHP实现二分查找算法的方法是什么,具有一定借鉴价值,需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获。下面让小编带着大家一起了解一下。
二分查找又称折半查找,二分查找算法要求数据必须是有序的,以下是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; } } 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的值。
感谢你能够认真阅读完这篇文章,希望小编分享PHP实现二分查找算法的方法是什么内容对大家有帮助,同时也希望大家多多支持亿速云,关注亿速云行业资讯频道,遇到问题就找亿速云,详细的解决方法等着你来学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。