IMCSI

php算法之二分查找

首先是二分查找算法的前提:

1.必须是索引数组,即键为数字

2.必须是已经排好序的数字,即键从小到大或者从大到小排序

1
2
3
4
5
6
7
8
9
10
11
12
13
function bin_sch($array,  $low, $high, $k){
if ( $low <= $high){//判断开始点是否小于等于终点
$mid = intval(($low+$high)/2 );//向下取中点值
if ($array[$mid] == $k){//如果刚好等于中点值则返回
return $mid;
}elseif ( $k < $array[$mid]){//若目标值小于中点值则从起点值到中点值-1范围内继续递归查找直到找到目标值的下标
return bin_sch($array, $low, $mid-1, $k);
}else{//若目标值大于中点值则从中点值+1到查找终点范围内继续递归查找直到找到目标值的下标
return bin_sch($array, $mid+ 1, $high, $k);
}
}
return -1;
}

$array是目标数组,$low为查找起点,$high为查找终点,$k为目标值

比如在100里面找到23的位置
首先将100/2得到两边为大于50和小于50的两部分,再判断23是小于50,就继续在小于50的范围查,继续将50/2再与23进行比较,直到等于23取其位置(键)即可。

因为二分查找是将目标数一直除以2进行查找,取目标数要在最后一次查找才能找出,那么有关二分法查找算法的效率(性能)问题的一点说明:

1000个数据,约10次找出;2的10次方等于1024

100万个数据,约20次找出;2的20次方等于1048576

10亿个数据,约30次找出; 以此类推..

40亿个数据,约32次找出。 ..

上一篇