本文实例讲述了PHP二分查找算法。分享给大家供大家参考,具体如下:
binarySearch
二分查找采用的方法比较容易理解,以数组为例:
① 先取数组中间的值floor((low+top)/2),
② 然后通过与所需查找的数字进行比较,若比中间值大,则将首值替换为中间位置下一个位置,继续第一步的操作;若比中间值小,则将尾值替换为中间位置上一个位置,继续第一步操作
③ 重复第二步操作直至找出目标数字
比如从1,3,9,23,54 中查找数字23,
首位置为0, 尾位置为4,中间位置就为2 值为9,比23小,则首位置更新为2+1即3;那么接下来中间位置就为(3+4)/2=3,值为23,比较相等即找到
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 非递归算法:
// $target是要查找的目标 $arr是已经排序好的数组
function binary(& $arr , $low , $top , $target ){
while ( $low <= $top ){
//由于php取商是有小数的,所以向下取整,不过也可不加,数组也会取整
$mid = floor (( $low + $top )/2);
echo $mid . "<br>" ;
if ( $arr [ $mid ]== $target ){
return $arr [ $mid ];
} elseif ( $arr [ $mid ]< $target ){
$low = $mid +1;
} else {
$top = $mid -1;
}
}
return -1;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 递归算法:
function binaryRecursive(& $arr , $low , $top , $target ){
if ( $low <= $top ){
$mid = floor (( $low + $top )/2);
if ( $mid == $target ){
return $arr [ $mid ];
} elseif ( $arr [ $mid ]< $target ){
return binaryRecursive( $arr , $mid +1, $top , $target );
} else {
return binaryRecursive( $arr , $low , $top -1, $target );
}
} else {
return -1;
}
}
|
希望本文所述对大家PHP程序设计有所帮助。