PHP二分查找算法的实现方法示例

本文实例讲述了PHP二分查找算法的实现方法。分享给大家供大家参考，具体如下：

二分查找法需要数组是一个有序的数组,假设我们的数组是一个递增的数组，首先我们需要找到数组的中间位置.

1. 要知道中间位置就需要知道起始位置和结束位置，然后取出中间位置的值来和我们的值做对比。

2. 如果中间值大于我们的给定值，说明我们的值在中间位置之前，此时需要再次二分，因为在中间之前，所以我们需要变的值是结束位置的值，此时结束位置的值应该是我们此时的中间位置。

3. 反之，如果中间值小于我们给定的值，那么说明给定值在中间位置之后，此时需要再次将后一部分的值进行二分，因为在中间值之后，所以我们需要改变的值是开始位置的值，此时开始位置的值应该是我们此时的中间位置，直到我们找到指定值。

4. 或者中间值等于最初的起始位置，或结束位置（此时说明给定值未找到），下面我们来用代码实现~

1. //循环实现 
2. function getValue($num,$arr) 
3. { 
4.   //查找数组的中间位置 
5.   $length=count($arr); 
6.   $start=0; 
7.   $end=$length; 
8.   $middle=floor(($start+$end)/2); 
9.   //循环判断 
10.   while($start>$end-1) 
11.   { 
12.     if($arr[middle]==$num) 
13.     { 
14.       return middle+1; 
15.     } elseif($arr[middle]<$num) 
16.     { 
17.       //如果当前要查找的值比当前数组的中间值还要打，那么意味着该值在数组的后半段 
18.       //所以起始位置变成当前的middle的值，end位置不变。 
19.       $start=$middle; 
20.       $middle=floor(($start+$end)/2); 
21.     } else{ 
22.       //反之 
23.       $end=$middle; 
24.       $middle=floor(($start+$end)/2); 
25.     } 
26.   } 
27.   return false; 
28. } 
29.  
30. //递归实现 
31. /* 
32. * 从数组中获取元素值 
33. * @param1 int $num，要查找的目标值 
34. * @param2 array $arr，要查找的数组 
35. * @param3 int $start，查找的起始位置 
36. * @param4 int $end，查找的结束位置 
37. * @return mixed，找到了返回位置，没找到返回false 
38. */ 
39. function getValue4($num,$arr,$start = 0,$end = 100){ 
40.     //采用二分法查找 
41.     $middle = floor(($end + $start) / 2); 
42.     //判断 
43.     if($arr[$middle] == $num){ 
44.       //已经找到了，递归的出口 
45.       return $middle + 1; 
46.     }elseif($arr[$middle] < $num){ 
47.       //要查找的元素在数组的后半段 
48.       $start = $middle + 1; 
49.       //边界值 
50.       if($start >= $end){ 
51.         //没有找到，但是已经超出边界值，递归出口 
52.         return false; 
53.       } 
54.       //调用自己去查找：递归点 
55.       return getValue4($num,$arr,$start,$end);  //getValue4($num,$arr,51,100) 
56.     }else{ 
57.       //要查找的元素在数组的前半段 
58.       $end = $middle - 1; 
59.       //判断边界值 
60.       if($end < 0)return false; 
61.       //调用自己：递归点 
62.       return getValue4($num,$arr,$start,$end);  //getValue4($num,$arr,0,49) 
63.     } //Vevb.com 
64.     //都没有找到 
65.     return false; 
66. }