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

分享到：