这篇文章主要介绍了PHP有序表查找之二分查找（折半查找）算法,简单介绍了二分查找法的概念、原理并结合实例形式分析了php基于二分查找算法进行有序线性表查找的相关操作技巧,需要的朋友可以参考下。

本文实例讲述了PHP有序表查找之二分查找（折半查找）算法，分享给大家供大家参考，具体如下：

简介：

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

基本思想：

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

代码：

1. <?php 
2. //二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn) 
3. $i = 0; //存储对比的次数 
4. //@param 待查找数组 
5. //@param 待搜索的数字 
6. function binsearch($arr,$num){ 
7.  $count = count($arr); 
8.  $lower = 0; 
9.  $high = $count - 1; 
10.  global $i; 
11.  while($lower <= $high){ 
12.   $i ++; //计数器 
13.   if($arr[$lower] == $num){ 
14.    return $lower; 
15.   } 
16.   if($arr[$high] == $num){ 
17.    return $high; 
18.   } 
19.   $middle = intval(($lower + $high) / 2); 
20.   if($num < $arr[$middle]){ 
21.    $high = $middle - 1; 
22.   }else if($num > $arr[$middle]){ 
23.    $lower = $middle + 1; 
24.   }else{ 
25.    return $middle; 
26.   } 
27.  } 
28.  //返回-1表示查找失败 
29.  return -1; 
30. } 
31. $arr = array(0,1,16,24,35,47,59,62,73,88,99); 
32. $pos = binsearch($arr,62); 
33. print($pos); 
34. echo "<br>"; 
35. echo $i; 

运行结果：

1. 1 
2. 2 
3. 7 
4. 3 

总结：

二叉查找的时间复杂度是 O(logn)。不过由于二叉查找的前提条件是需要有序表顺序存储（数组），如果该有序表需要频繁的执行插入或删除操作，维护有序的排序会带来不小的工作量。

Tags: PHP二分查找 PHP折半查找

分享到：