PHP二分算法查找的代码实现及详细分析

admin

PHP二分算法查找的代码实现及详细分析

PHP二分查找函数，Code：

1. /**
   
2. * 二分算法查找
   
3. * @param array $array 要查找的数组
   
4. * @param int $min_key 数组的最小下标
   
5. * @param int $max_key 数组的最大下标
   
6. * @param mixed $value 要查找的值
   
7. * @return boolean
   
8. */
   
9. function bin_search($array,$min_key,$max_key,$value){
   
10.     if($min_key <= $max_key){
    
11.         $key = intval(($min_key+$max_key)/2);
    
12.         if($array[$key] == $value){
    
13.             return true;
    
14.         }elseif($value < $array[$key]){
    
15.             return bin_search($array,$min_key,$key-1,$value);
    
16.         }else{
    
17.             return bin_search($array,$key+1,$max_key,$value);
    
18.        }
    
19.     }else{
    
20.         return false;
    
21.     }
    
22. }
    
23. 
    
24. //现在我们来测试一下这个函数
    
25. $array = array(1,22,23,45,58);
    
26. $value = 45;
    
27. $min_key = min(array_keys($array));
    
28. $max_key = max(array_keys($array));
    
29. if(bin_search($array,$min_key,$max_key,$value)){
    
30.     echo "Search Success!";
    
31. }else{
    
32.     echo "Search Faliure!";
    
33. }

复制代码

这样就实现了二分查找的功能了，是不是很简单呢?
这里涉及到了两个知识点:
首先是二分算法的概念:如下
1、二分查找的先决条件:就是表中结点按关键字有序，且顺序(一维数组)存储.
2、二分法思想:取中,比较
(2.1)求有序表的中间位置mid
(2.2)若r[mid].key == k,则查找成功,若r[mid].key > k,在左子表中继续进行二分查找;若r[mid].key < k,则在右字表中继续进行二分查找
然后就是 递归了，这个大家都比较熟悉，在此就不多说了。