二分法查找

二分法查找 （递归法）

function Search($arr,$val,$start,$stop){
    //确定中间值的索引
    $mkey=ceil(($start+$stop)/2);
    //如果中间值等于查找值返回索引
    if($arr[$mkey] == $val){
        return $mkey;
    }
    //如果中间值大于查找值，则查找值在中间值的左半部分，开始位置不变，结束位置为中间值索引减一
    if($arr[$mkey] > $val){
        $stop=$mkey-1;
    }
    //如果中间值小于查找值，则查找值在中间值的右半部分，结束位置不变，开始位置为中间值索引加一
    if($arr[$mkey] < $val){
        $start=$mkey+1;
    }
    //如果结束位置小于开始位置，则数组中没有该数值，返回false
    if($stop<$start){
        return false;
    }
    return Search($arr,$val,$start,$stop);
}
//$arr=[2,7,8,10,15,19,23,39,40,44,50,51,66];
//$val=34;
//var_dump(Search($arr,$val,0,count($arr)-1)) ;

二分法查找（非递归法）

function LoopSearch($arr,$val,$start,$stop){
    while($start<=$stop){//确定中间值的索引
        $mkey=ceil(($start+$stop)/2);
        //如果中间值等于查找值返回索引
        if($arr[$mkey] == $val){
            return $mkey;
        }
        //如果中间值大于查找值，则查找值在中间值的左半部分，开始位置不变，结束位置为中间值索引减一
        if($arr[$mkey] > $val){
            $stop=$mkey-1;
        }
        //如果中间值小于查找值，则查找值在中间值的右半部分，结束位置不变，开始位置为中间值索引加一
        if($arr[$mkey] < $val){
            $start=$mkey+1;
        }
    }
}

$arr=[2,7,8,10,15,19,23,39,40,44,50,51,66];
$val=44;
var_dump(LoopSearch($arr,$val,0,count($arr)-1)) ;