本文实例讲述了PHP实现的折半查询算法。分享给大家供大家参考,具体如下:
什么是折半查询算法?具体文字描述自己百度。直接上代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
<?php
header( "Content-type: text/html; charset=utf-8" );
/* 折半查询算法--不用递归 */
function qSort( $data = array (), $x = 0){
$startIndex = 0; // 开始索引
$endIndex = count ( $data ) - 1; // 结束索引
$index = 0;
$number = 0; // 计数器
do {
if ( $endIndex > $startIndex ){
$searchIndex = ceil (( $endIndex - $startIndex ) / 2);
} else if ( $endIndex == $startIndex ){
$searchIndex = $endIndex ;
} else {
$index = -1;
break ;
}
$searchIndex += ( $startIndex - 1);
echo '检索范围:' . $startIndex . ' ~ ' . $endIndex . '<br>检索位置:' . $searchIndex . '检索值为:' . $data [ $searchIndex ];
echo '<br>=======================<br><br>' ;
if ( $data [ $searchIndex ] == $x ){
$index = $searchIndex ;
break ;
} else if ( $x > $data [ $searchIndex ]){
$startIndex = $searchIndex + 1;
} else {
$endIndex = $searchIndex - 1;
}
$number ++;
} while ( $number < count ( $data ));
return $index ;
}
/* 折半查询算法--使用递归 */
function sSort( $data , $x , $startIndex , $endIndex ){
if ( $endIndex > $startIndex ){
$searchIndex = ceil (( $endIndex - $startIndex ) / 2);
} else if ( $endIndex == $startIndex ){
$searchIndex = $endIndex ;
} else {
return -1;
}
$searchIndex += ( $startIndex - 1);
echo '检索范围:' . $startIndex . ' ~ ' . $endIndex . '<br>检索位置:' . $searchIndex . '检索值为:' . $data [ $searchIndex ];
echo '<br>=======================<br><br>' ;
if ( $data [ $searchIndex ] == $x ){
return $searchIndex ;
} else if ( $x > $data [ $searchIndex ]){
$startIndex = $searchIndex + 1;
return sSort( $data , $x , $startIndex , $endIndex );
} else {
$endIndex = $searchIndex - 1;
return sSort( $data , $x , $startIndex , $endIndex );
}
}
$data = array (1, 3, 4, 6, 9, 11, 12, 13, 15, 20, 21, 25, 33, 34, 35, 39, 41, 44);
$index = qSort( $data , 11); // 不用递归的排序方法
$index = sSort( $data , 11, 0, count ( $data ) - 1); // 使用递归的排序方法
echo '结果:' . $index ;
|
运行结果:
希望本文所述对大家PHP程序设计有所帮助。
原文链接:http://blog.csdn.net/mxdzchallpp/article/details/51038816