当前位置:Gxlcms > PHP教程 > PHP如何实现二进制搜索?(代码示例)

PHP如何实现二进制搜索?(代码示例)

时间:2021-07-01 10:21:17 帮助过:28人阅读

二进制搜索(折半查找)是一种用于搜索排序数组中元素的搜索技术。那么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
        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: 不存在

以上就是本篇文章的全部内容,希望能对大家的学习有所帮助。更多精彩内容大家可以关注Gxl网相关教程栏目!!!

以上就是PHP如何实现二进制搜索?(代码示例)的详细内容,更多请关注Gxl网其它相关文章!

人气教程排行