上次写个二分查找，错误百出，唉，还真如编程珠玑里面说的，写二分查找的人 90%都不会一次成功。深深的鄙视一下自己，贴一下二分的代码，以及二分查找的变种代码

1. //二分查找 
2. function binary _search($search, $data_arr, $lower, $upper) 
3. { 
4.     if($lower > $upper) 
5.     { 
6.         return false; 
7.     } 
8.      
9.     $mid = intval( ($lower + $upper) / 2 ); 
10.      
11.     if($search == $data_arr[$mid]) 
12.     { 
13.         return $mid; 
14.     }elseif($search < $data_arr[$mid]) 
15.     { 
16.         $upper = $mid - 1; 
17.     }else 
18.     { 
19.         $lower = $mid + 1; 
20.     } 
21.      
22.     return search($search, $data_arr, $lower, $upper); 
23. } 
24.  
25. /* 
26.  * 二分查找变种，查找$search第一次出现的位置 ,对于传值，$lower=-1  $upper=count($data_arr)
27.  *  
28.  * array(0,2,3,7,8,8,8,9,10) 
29.  * binary_search_begin(8, ....) 
30.  * 返回值4 
31.  */ 
32. function binary_search_begin($search, $data_arr, $lower, $upper) 
33. { 
34.     if( ($lower + 1) == $upper ) 
35.     { 
36.         return ($data_arr[$upper] == $search)? $upper : -1; 
37.     } 
38.      
39.     $mid = intval( ($lower + $upper) / 2 ); 
40.      
41.     if( $data_arr[$mid] < $search ) 
42.     { 
43.         $lower = $mid; 
44.     }else  
45.     { 
46.         $upper = $mid; 
47.     } 
48.      
49.     return binary_search_begin($search, $data_arr, $lower, $upper); 
50. } 
51.  
52. /* 
53.  * 二分查找变种，查找$search最后一次出现的位置 ,对于传值，$lower=-1  $upper=count($data_arr)
54.  * array(0,2,3,7,8,8,8,9,10) 
55.  * binary_search_begin(8, ....) 
56.  * 返回值6 
57.  */ 
58. function binary_search_end($search, $data_arr, $lower, $upper) 
59. { 
60.     if( ($lower + 1) == $upper ) 
61.     { 
62.         return ($data_arr[$lower] == $search)? $lower : -1; 
63.     } 
64.      
65.     $mid = intval( ($lower + $upper) / 2 ); 
66.      
67.     if( $data_arr[$mid] > $search ) 
68.     { 
69.         $upper = $mid; 
70.     }else  
71.     { 
72.         $lower = $mid; 
73.     } 
74.      
75.     return binary_search_end($search, $data_arr, $lower, $upper); 
76. } 

其迭代方法的实现为：

1. //二分查找 
2. function binary_search($search, $data_arr, $lower, $upper) 
3. { 
4.     while($lower <= $upper) 
5.     { 
6.         $mid = intval( ($lower + $upper) / 2 ); 
7.          
8.         if($data_arr[$mid] > $search) 
9.         { 
10.             $upper = $mid - 1; 
11.         }elseif($data_arr[$mid] < $search) 
12.         { 
13.             $lower = $mid + 1; 
14.         }else  
15.         { 
16.             return $mid; 
17.         } 
18.     } 
19.      
20.     return false; 
21. } 
22.  
23. /* 
24.  * 二分查找变种，查找$search第一次出现的位置,对于传值，$lower=-1  $upper=count($data_arr) 
25.  * array(0,2,3,7,8,8,8,9,10) 
26.  * binary_search_begin(8, ....) 
27.  * 返回值4 
28.  */ 
29. function binary_search_begin($search, $data_arr, $lower, $upper) 
30. { 
31.     while($lower + 1 != $upper) 
32.     { 
33.         $mid = intval( ($lower + $upper) / 2 ); 
34.          
35.         if($data_arr[$mid] < $search) 
36.         { 
37.             $lower = $mid; 
38.         }else  
39.         { 
40.             $upper = $mid; 
41.         } 
42.          
43.         $p = $upper; 
44.          
45.         if($data_arr[$p] != $search) 
46.         { 
47.             $p = false; 
48.         } 
49.     } 
50.      
51.     return $p; 
52. } 
53.  
54. /* 
55.  * 二分查找变种，查找$search最后一次出现的位置，对于传值，$lower=-1  $upper=count($data_arr) 
56.  * array(0,2,3,7,8,8,8,9,10) 
57.  * binary_search_begin(8, ....) 
58.  * 返回值6 
59.  */ 
60. function binary_search_end($search, $data_arr, $lower, $upper) 
61. { 
62.     while($lower + 1 != $upper) 
63.     { 
64.         $mid = intval( ($lower + $upper) / 2 ); 
65.          
66.         if($data_arr[$mid] > $search) 
67.         { 
68.             $upper = $mid; 
69.         }else  
70.         { 
71.             $lower = $mid; 
72.         } 
73.          
74.         $p = $lower; 
75.         if($data_arr[$p] != $search) 
76.         { 
77.             $p = false; 
78.         } 
79.     } 
80.      
81.     return $p; 
82.      
83. }