PHP实现二分查找算法（代码详解）

二分查找又称折半查找，二分查找算法要求数据必须是有序的，以下是php实现二分查找算法的代码。

一：递归方式

1. $array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89]; 
2.  
3. $target = 73; 
4.  
5. $low = 0; 
6.  
7. $high = count($array)-1; 
8.  
9. function bin_search($array, $low, $high, $target){ 
10.  
11.     if ( $low <= $high){ 
12.  
13.         var_dump($low, $high);echo "/n"; 
14.  
15.         $mid =  intval(($low+$high)/2 ); 
16.  
17.         if ($array[$mid] ==  $target){ 
18.  
19.             return true; 
20.  
21.         }elseif ( $target < $array[$mid]){ 
22.  
23.             return  bin_search($array, $low,  $mid-1, $target); 
24.  
25.         }else{ 
26.  
27.             return  bin_search($array, $mid+ 1, $high, $target); 
28.  
29.         } 
30.  
31.     } 
32.  
33.     return false; 
34.  
35. } 
36.  
37. $find = bin_search($array, $low, $high, $target); 
38.  
39. var_dump($find); 

执行结果

1. int(0) 
2.  
3. int(25) 
4.  
5. int(13) 
6.  
7. int(25) 
8.  
9. int(20) 
10.  
11. int(25) 
12.  
13. int(20) 
14.  
15. int(21) 
16.  
17. bool(true) 

我们看到，经过4次二分查找，查找区间不断折半，最终找到了$target。

二：循环方式

1. $array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89]; 
2.  
3. $target = 73; 
4.  
5. function bin_search($array, $target) 
6.  
7. { 
8.  
9.     $low = 0; 
10.  
11.     $high = count($array)-1; 
12.  
13.     $find = false; 
14.  
15.     while (true){ 
16.  
17.         if ($low <= $high){ 
18.  
19.             var_dump($low, $high);echo "/n"; 
20.  
21.             $mid = intval(($low + $high)/2); 
22.  
23.             if ($array[$mid] == $target){ 
24.  
25.                 $find = true; 
26.  
27.                 break; 
28.  
29.             } elseif ($array[$mid] < $target){ 
30.  
31.                 $low = $mid+1; 
32.  
33.             } elseif ($array[$mid] > $target){ 
34.  
35.                 $high = $mid-1; 
36.  
37.             } 
38.  
39.         } else { 
40.  
41.             break; 
42.  
43.         } 
44.  
45.     } 
46.  
47.     return $find; 
48.  
49. } 
50.  
51. $find = bin_search($array, $target); 
52.  
53. var_dump($find); 

执行结果

1. int(0) 
2.  
3. int(25) 
4.  
5. int(13) 
6.  
7. int(25) 
8.  
9. int(20) 
10.  
11. int(25) 
12.  
13. int(20) 
14.  
15. int(21) 
16.  
17. bool(true) 

我们看到，两种方式过程和结果相同。下面我们来测试下针对关联数组的二分查找算法：

1. $array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38]; 
2.  
3. $target = 19; 
4.  
5. function bin_search($array, $target) 
6.  
7. { 
8.  
9.     $low = 0; 
10.  
11.     $high = count($array)-1; 
12.  
13.     $key_map = array_keys($array); 
14.  
15.     $find = false; 
16.  
17.     while (true){ 
18.  
19.         if ($low <= $high){ 
20.  
21.             var_dump($low, $high);echo "/n"; 
22.  
23.             $mid = intval(($low + $high)/2); 
24.  
25.             if ($array[$key_map[$mid]] == $target){ 
26.  
27.                 $find = true; 
28.  
29.                 break; 
30.  
31.             } elseif ($array[$key_map[$mid]] < $target){ 
32.  
33.                 $low = $mid+1; 
34.  
35.             } elseif ($array[$key_map[$mid]] > $target){ 
36.  
37.                 $high = $mid-1; 
38.  
39.             } 
40.  
41.         } else { 
42.  
43.             break; 
44.  
45.         } 
46. //Vevb.com 
47.     } 
48.  
49.     return $find; 
50.  
51. } 
52.  
53. $find = bin_search($array, $target); 
54.  
55. var_dump($find); 

执行结果

1. int(0) 
2.  
3. int(8) 
4.  
5. int(5) 
6.  
7. int(8) 
8.  
9. bool(true) 

两次二分查找，找到了$target，针对关联数组，我们使用了php的array_keys函数获得这个关联有序数组的key，通过key间接比对$target和$array的值。