php的二分查找算法

之前学习了mysql的Btree类型索引的原理，就是通过二分查找的方式对数据进行快速检索。再来重新整理php代码实现二分查找的过程。

思想：

比如有从小到大排列好（排列好是关键）的1-10000的数据，对于要查找的数据可以从中拦截，先判断是否等于要查找的数字，相等直接返回。不相等，判断大小，指定向左（小于的区间）和向右查找（大于区间）。依次递归，直至查找到要查找的内容。优点是每次递归，将查找的复杂度降低一半。

关键:

要对数据进行排列

代码：

function binsearch($x,$a){

    $c=count($a);

    $lower=0;

    $high=$c-1;

    while($lower<=$high){

        $middle=intval(($lower+$high)/2);

        if($a[$middle]>$x){

            $high=$middle-1;

        } elseif($a[$middle]<$x){

            $lower=$middle+1;

        } else{

            return$middle;

        }

    }

    return-1;

}