php算法之二分查找

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

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

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

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次找出。 ..