方法一:使用迭代
步骤:
1、对数组进行排序,因为二进制搜索仅适用于已排序的范围
2、如果我们要搜索的元素大于右侧的中间元素搜索,则计算中间元素,否则计算左侧的搜索。
3、如果找到元素,则返回True。
实现代码:
?php header( content-type:text/html;charset=utf-8 function binarySearch(Array $arr, $x) // check for empty array if (count($arr) === 0) return false; $low = 0; $high = count($arr) - 1; while ($low = $high) { // 计算中间索引 $mid = floor(($low + $high) / 2); // 在中间找到元素 if($arr[$mid] == $x) { return true; if ($x $arr[$mid]) { // 搜索数组的左侧 $high = $mid -1; else { // 搜索数组的右侧 $low = $mid + 1; // 元素x不存在,返回false return false; $arr = array(1, 2, 3, 4, 5); $value = 5; if(binarySearch($arr, $value) == true) { echo 元素 .$value. : 存在 else { echo 元素 .$value. : 不存在 ?
输出:
元素5: 存在
方法二:使用递归
递归是我们重复调用相同函数直到匹配基本条件以结束递归的方式。原理和方法一相同,只需以递归的方式更改函数的参数并分解问题。
实现代码:
?php header( content-type:text/html;charset=utf-8 function binarySearch(Array $arr, $start, $end, $x){ if ($end $start) return false; $mid = floor(($end + $start)/2); if ($arr[$mid] == $x) return true; elseif ($arr[$mid] $x) { // 调用binarySearch()函数本身, 改变其中参数:$start, $mid-1 return binarySearch($arr, $start, $mid - 1, $x); else { // 调用binarySearch()函数本身, 改变其中参数:mid + 1, end return binarySearch($arr, $mid + 1, $end, $x); $arr = array(1, 2, 3, 4, 5); $value = 6; if(binarySearch($arr, 0, count($arr) - 1, $value) == true) { echo 元素 .$value. : 存在 else { echo 元素 .$value. : 不存在 ?
输出:
元素6: 不存在
以上就是本篇文章的全部内容,希望能对大家的学习有所帮助。更多精彩内容大家可以关注php 相关教程栏目!!!
以上就是PHP如何实现二进制搜索?(代码示例)的详细内容,PHP教程
郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。
新闻热点
疑难解答