这篇文章主要介绍了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实现二分查找算法的方法是什么内容对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，遇到问题就找亿速云，详细的解决方法等着你来学习!
亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
