这篇文章主要介绍了PHP实现的折半查找算法,简单描述了折半查找的原理,并结合实例形式分析了php采用递归与非递归方式实现折半查找算法的相关操作技巧,需要的朋友可以参考下

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

定义：折半查找技术，也就是二分查找。它的前提是线性表中的记录必须是关键码有序（通常从大到小有序），线性表必须采用顺序存储。

折半查找的基本思想：取中间记录作为比较对象，若给定值与中间记录的关键字，则在中间记录的关键字相等，则查找成功；若给定值小于中间记录的作伴去继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止。

实现代码：

1. <?php 
2. //递归方式 
3. function bin_recur_search($arr,$val){ 
4.   global $time; 
5.   if(count($arr) >= 1){ 
6.     $mid = intval(count($arr) / 2); 
7.     $time++; 
8.     if($arr[$mid] == $val){ 
9.       return '值为:'.$arr[$mid].'<br>查找次数：'.$time.'<br>'; 
10.     }elseif($arr[$mid] > $val){ 
11.       $arr = array_splice($arr,0,$mid); 
12.       return bin_recur_search($arr, $val); 
13.     }else{ 
14.       $arr = array_slice($arr,$mid + 1); 
15.       return bin_recur_search($arr, $val); 
16.     } 
17.   } 
18.   return '未找到'.$val; 
19. } 
20. //非递归方式 
21. function bin_search($arr,$val){ 
22.   if(count($arr) >= 1){ 
23.     $low = 0; 
24.     $high = count($arr); 
25.     $time = 0; 
26.     while($low <= $high){ 
27.       $time++; 
28.       $mid = intval(($low + $high)/2); 
29.       if($val == $arr[$mid]){ 
30.         return '索引：'.$mid.'<br>值为：'.$arr[$mid].'<br>查找次数：'.$time; 
31.       }elseif($val > $arr[$mid]){ 
32.         $low = $mid + 1; 
33.       }else{ 
34.         $high = $mid - 1; 
35.       } 
36.     } 
37.   } 
38.   return '未找到'.$val; 
39. } 
40. $arr = array(1,3,5,7,7,9,25,68,98,145,673,8542); 
41. echo bin_recur_search($arr, 673); 
42. echo bin_search($arr, 673); 
43. ?> 

运行结果：

1. 值为:673 
2. 查找次数：4 
3. 索引：10 
4. 值为：673 
5. 查找次数：4

Tags: PHP折半查找算法

分享到：