PHP如何实现二进制搜索？（代码示例）

二进制搜索（折半查找）是一种用于搜索排序数组中元素的搜索技术。那么PHP中如何实现二进制搜索？下面本篇文章就来给大家介绍在PHP中如何使用迭代和递归方式来实现二进制搜索，希望对大家有所帮助。

方法一：使用迭代

步骤：

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 <mark>@本文来源gaodaimacom搞#代%码@网-</mark><strong>搞代gaodaima码</strong>       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如何实现二进制搜索？（代码示例）的详细内容，更多请关注搞代码gaodaima其它相关文章！

喜欢 (0)赏

[搞代码]

分享 (0)