当前位置:首页 > PHP教程 > php应用 > 列表

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

发布:smiling 来源: PHP粉丝网  添加日期:2020-01-29 10:52:55 浏览: 评论:0 

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

方法一:使用迭代

步骤:

1、对数组进行排序,因为二进制搜索仅适用于已排序的范围

2、如果我们要搜索的元素大于右侧的中间元素搜索,则计算中间元素,否则计算左侧的搜索。

3、如果找到元素,则返回True。

实现代码:

  1. <?php  
  2.  
  3. header("content-type:text/html;charset=utf-8"); 
  4.  
  5. function binarySearch(Array $arr$x)  
  6.  
  7. {  
  8.  
  9.     // check for empty array  
  10.  
  11.     if (count($arr) === 0) return false;  
  12.  
  13.     $low = 0;  
  14.  
  15.     $high = count($arr) - 1;  
  16.  
  17.         
  18.  
  19.     while ($low <= $high) {  
  20.  
  21.             
  22.  
  23.         // 计算中间索引 
  24.  
  25.         $mid = floor(($low + $high) / 2);  
  26.  
  27.      
  28.  
  29.         // 在中间找到元素 
  30.  
  31.         if($arr[$mid] == $x) {  
  32.  
  33.             return true;  
  34.  
  35.         }  
  36.  
  37.     
  38.  
  39.         if ($x < $arr[$mid]) {  
  40.  
  41.             // 搜索数组的左侧 
  42.  
  43.             $high = $mid -1;  
  44.  
  45.         }  
  46.  
  47.         else {  
  48.  
  49.             // 搜索数组的右侧 
  50.  
  51.             $low = $mid + 1;  
  52.  
  53.         }  
  54.  
  55.     }  
  56.  
  57.         
  58.  
  59.     // 元素x不存在,返回false 
  60.  
  61.     return false;  
  62.  
  63. }  
  64.  
  65.     
  66.  
  67. $arr = array(1, 2, 3, 4, 5);  
  68.  
  69. $value = 5;  
  70.  
  71. if(binarySearch($arr$value) == true) {  
  72.  
  73.     echo "元素".$value.": 存在";  
  74.  
  75. }  
  76. //phpfensi.com 
  77. else {  
  78.  
  79.     echo "元素".$value.": 不存在";  
  80.  
  81. }  
  82.  
  83. ?> 

输出:

元素5: 存在

方法二:使用递归

递归是我们重复调用相同函数直到匹配基本条件以结束递归的方式。原理和方法一相同,只需以递归的方式更改函数的参数并分解问题。

实现代码:

  1. <?php  
  2.  
  3. header("content-type:text/html;charset=utf-8"); 
  4.  
  5. function binarySearch(Array $arr$start$end$x){  
  6.  
  7.     if ($end < $start)  
  8.  
  9.         return false;  
  10.  
  11.      
  12.  
  13.     $mid = floor(($end + $start)/2);  
  14.  
  15.     if ($arr[$mid] == $x)   
  16.  
  17.         return true;  
  18.  
  19.     
  20.  
  21.     elseif ($arr[$mid] > $x) {  
  22.  
  23.     
  24.  
  25.         // 调用binarySearch()函数本身, 改变其中参数:$start, $mid-1 
  26.  
  27.         return binarySearch($arr$start$mid - 1, $x);  
  28.  
  29.     }  
  30.  
  31.     else {  
  32.  
  33.     
  34.  
  35.         // 调用binarySearch()函数本身, 改变其中参数:mid + 1, end 
  36.  
  37.         return binarySearch($arr$mid + 1, $end$x);  
  38.  
  39.     }  
  40.  
  41. }  
  42.  
  43.     
  44.  
  45. $arr = array(1, 2, 3, 4, 5);  
  46.  
  47. $value = 6;  
  48.  
  49. if(binarySearch($arr, 0, count($arr) - 1, $value) == true) {  
  50.  
  51.     echo "元素".$value.": 存在";  
  52.  
  53. }  
  54.  
  55. else {  
  56.  
  57.     echo "元素".$value.": 不存在";  
  58.  
  59. }  
  60.  
  61. ?> 

输出:

元素6: 不存在

以上就是本篇文章的全部内容,希望能对大家的学习有所帮助。

Tags: PHP二进制搜索

分享到: