这篇文章主要介绍了php二分查找的二种实现示例，递归解法二分查找和非递归算法二分查找的示例,需要的朋友可以参考下。

php二分查找示例

二分查找常用写法有递归和非递归，在寻找中值的时候，可以用插值法代替求中值法。

当有序数组中的数据均匀递增时，采用插值方法可以将算法复杂度从中值法的lgN减小到lglgN，代码如下:

1. /** 
2.  * 二分查找递归解法 
3.  * @param type $subject 
4.  * @param type $start 
5.  * @param type $end 
6.  * @param type $key 
7.  * @return boolean 
8.  */ 
9. function binarySearch_r($subject, $start, $end, $key) 
10. { 
11.  
12.  if ( $start >= $end ) return FALSE; 
13.  $mid = getMidKey($subject, $start, $end, $key); 
14.  if ( $subject[$mid] == $key ) return $mid; 
15.  if ( $key > $subject[$mid] ) { 
16.   return binarySearch($subject, $mid, $end, $key); 
17.  } 
18.  if ( $key <= $subject[$mid] ) { 
19.   return binarySearch($subject, $start, $mid, $key); 
20.  } 
21. } 
22.  
23. /** 
24.  * 二分查找的非递归算法 
25.  * @param type $subject 
26.  * @param type $n 
27.  * @param type $key 
28.  */ 
29. function binarySearch_nr($subject, $n, $key) 
30. { 
31.  $low = 0; 
32.  $high = $n; 
33.  while ( $low <= $high ) { 
34.   $mid = getMidKey($subject, $low, $high, $key); 
35.   if ( $subject[$mid] == $key ) return $mid; 
36.   if ( $subject[$mid] < $key ) { 
37.    $low = $mid + 1; 
38.   } 
39.   if ( $subject[$mid] > $key ) { 
40.    $high = $mid - 1; 
41.   } 
42.  } 
43. } 
44. function getMidKey($subject, $low, $high, $key) 
45. { 
46.  /** 
47.   * 取中值算法1 取中值 不用 ($low+$high)/2的方式是因为 防止low和high较大时候，产生溢出.... 
48.   */ 
49.  //return round($low + ($high - $low) / 2); 
50. //phpfensi.com 
51.  /** 
52.   * 经过改进的插值算法求中值，当数值分布均匀情况下，再降低算法复杂度到lglgN 
53.   * 取中值算法2 
54.   */ 
55.  return round( (($key - $subject[$low]) / ($subject[$high] - $subject[$low])*($high-$low) ) ); 
56. } 

Tags: php二分查找

分享到：