数据结构-对分查找之寻找下标 可刷新运行 刷新

算法开销O(NLogN),如果数据提前放在内存中,算法开销为O(LogN)

代码:

$arr=[1,2,3,4,6,8];
function binarySearch($arr,$search){

    $low=0;
    $high=count($arr)-1;

    while ($low<=$high){
        $middle=(int)(($low+$high)/2);
        if($arr[$middle]<$search){
            $low=$middle+1;
        }else if ($arr[$middle]>$search){
            $high=$middle-1;
        }else{
            return $middle;
        }
    }
    return -1;

}
echo binarySearch($arr,4)."\n";

输出:

3
遇到问题?