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： 不存在

关于PHP实现二进制搜索的方法介绍就分享到这里了，当然并不止以上和大家分析的办法，不过小编可以保证其准确性是绝对没问题的。希望以上内容可以对大家有一定的参考价值，可以学以致用。如果喜欢本篇文章，不妨把它分享出去让更多的人看到。

关于 "PHP实现二进制搜索的方法介绍" 就介绍到此。希望多多支持编程宝库。

怎么使用PHP计算素数小于100的和：本文讲解"如何使用PHP计算素数小于100的和"，用于解决相关问题。素数又叫质数(prime number),有无限个。质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。那么我们想要用PH ...