这篇文章主要介绍了PHP实现的折半查询算法,结合完整实例形式分析了php使用递归与非递归实现折半查询的算法操作步骤与使用方法,需要的朋友可以参考下

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

什么是折半查询算法？具体文字描述自己百度，直接上代码：

1. <?php 
2. header("Content-type: text/html; charset=utf-8"); 
3. /* 折半查询算法--不用递归 */ 
4. function qSort($data = array(), $x = 0){ 
5.  $startIndex = 0;    // 开始索引 
6.  $endIndex = count($data) - 1; // 结束索引 
7.  $index = 0; 
8.  $number = 0;     // 计数器 
9.  do{ 
10.   if($endIndex > $startIndex){ 
11.    $searchIndex = ceil(($endIndex - $startIndex) / 2); 
12.   }else if($endIndex == $startIndex){ 
13.    $searchIndex = $endIndex; 
14.   }else{ 
15.    $index = -1; 
16.    break; 
17.   } 
18.   $searchIndex += ($startIndex - 1); 
19.   echo '检索范围：'.$startIndex.' ~ '.$endIndex.'<br>检索位置：'.$searchIndex.'检索值为：'.$data[$searchIndex]; 
20.   echo '<br>=======================<br><br>'; 
21.   if($data[$searchIndex] == $x){ 
22.    $index = $searchIndex; 
23.    break; 
24.   }else if($x > $data[$searchIndex]){ 
25.    $startIndex = $searchIndex + 1; 
26.   }else{ 
27.    $endIndex = $searchIndex - 1; 
28.   } 
29.   $number++; 
30.  }while($number < count($data)); 
31.  return $index; 
32. } 
33. /* 折半查询算法--使用递归 */ 
34. function sSort($data, $x, $startIndex, $endIndex){ 
35.  if($endIndex > $startIndex){ 
36.   $searchIndex = ceil(($endIndex - $startIndex) / 2); 
37.  }else if($endIndex == $startIndex){ 
38.   $searchIndex = $endIndex; 
39.  }else{ 
40.   return -1; 
41.  } 
42.  $searchIndex += ($startIndex - 1); 
43.  echo '检索范围：'.$startIndex.' ~ '.$endIndex.'<br>检索位置：'.$searchIndex.'检索值为：'.$data[$searchIndex]; 
44.  echo '<br>=======================<br><br>'; 
45.  if($data[$searchIndex] == $x){ 
46.   return $searchIndex; 
47.  }else if($x > $data[$searchIndex]){ 
48.   $startIndex = $searchIndex + 1; 
49.   return sSort($data, $x, $startIndex, $endIndex); 
50.  }else{ 
51.   $endIndex = $searchIndex - 1; 
52.   return sSort($data, $x, $startIndex, $endIndex); 
53.  } 
54. } 
55. $data = array(1, 3, 4, 6, 9, 11, 12, 13, 15, 20, 21, 25, 33, 34, 35, 39, 41, 44); 
56. $index = qSort($data, 11);      // 不用递归的排序方法 
57. $index = sSort($data, 11, 0, count($data) - 1); // 使用递归的排序方法 
58. echo '结果：'.$index;

Tags: PHP折半查询算法

分享到：