欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

折半查找&顺序查找

程序员文章站 2024-03-20 18:42:10
...

折半查找:


$i = 0;    //存储对比的次数

//@param 待查找数组
//@param 待搜索的数字
function binsearch($arr,$num){
    $count = count($arr);
    $lower = 0;
    $high = $count - 1;
    global $i;

    while($lower <= $high){

        $i ++; //计数器

        if($arr[$lower] == $num){
            return $lower;
        }
        if($arr[$high] == $num){
            return $high;
        }

        $middle = intval(($lower + $high) / 2);
        if($num < $arr[$middle]){
            $high = $middle - 1;
        }else if($num > $arr[$middle]){
            $lower = $middle + 1;
        }else{
            return $middle;
        }
    }

    //返回-1表示查找失败
    return -1;
}

$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = binsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

顺序查找;

$arr=array(46,90,900,0,-1);
//这是按顺序查询
function search(&$arr,$findVal){     
    $flag=false;
    for($i=0;$i<count($arr);$i++){
        if($findVal==$arr[$i]){
            echo "找到了,下标为=$i";
            $flag=true;
            //查询一次,如果多次就不要这个 break;
        }
    }
    if(!$flag){
        echo "查无此数";
    }
}