7968 - PHP递归二分查找法

admin

1. <?php
   
2.     /*
   
3.      * 从数组中获取元素值
   
4.      * @param1 int $num，要查找的目标值
   
5.      * @param2 array $arr，要查找的数组
   
6.      * @param3 int $start，查找的起始位置
   
7.      * @param4 int $end，查找的结束位置
   
8.      * @return mixed，找到了返回位置，没找到返回false
   
9.      */
   
10.      function getValue4($num,$arr,$start = 0,$end = 100){
    
11.         //确定起始和终止位置
    
12.         //采用二分法查找
    
13.         $middle = floor(($end + $start) / 2);
    
14.         //判断
    
15.         if($arr[$middle] == $num){
    
16.             //已经找到了，递归的出口
    
17.             return $middle + 1;
    
18.         }elseif($arr[$middle] < $num){
    
19.             //要查找的元素在数组的后半段
    
20.             $start = $middle + 1;
    
21.             //边界值
    
22.             if($start >= $end){
    
23.                 //没有找到，但是已经超出边界值，递归出口
    
24.                 return false;
    
25.             }
    
26.             //调用自己去查找：递归点
    
27.             return getValue4($num,$arr,$start,$end);    //getValue4($num,$arr,51,100)
    
28.         }else{
    
29.             //要查找的元素在数组的前半段
    
30.             $end = $middle - 1;
    
31.             //判断边界值
    
32.             if($end < 0)return false;
    
33.             //调用自己：递归点
    
34.             return getValue4($num,$arr,$start,$end);    //getValue4($num,$arr,0,49)
    
35.         }
    
36.         //都没有找到
    
37.         return false;
    
38.      }
    
39. $arr = array(1,2,3,4,5,34,56,78,88,99,100);
    
40. $num = 3;
    
41. $end = count($arr);
    
42. echo getValue4($num,$arr,0,$end);
    
43. ?>

复制代码