查找算法:二分查找法(折半查找)

仙士可

发布于 2019-12-18 15:07:57

1.1K0

发布于 2019-12-18 15:07:57

文章被收录于专栏：仙士可博客仙士可博客仙士可博客

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

猜数字游戏

大家都应该玩过猜数字的游戏吧?

给定一个数字的范围 1-100 随机抽取一个数字,然后玩家轮流猜数字,猜错时告诉玩家结果数字是大于猜测数字还是小于.

那么,该怎么猜数字最快得出答案呢?当然就是二分查找了:

二分查找猜数字

每次猜数字,都按照范围的一半进行猜测,例如

1-100范围,随机抽取55这个数字

折半查找猜50,大于50,那么这个数字的范围就缩小到了50-100,

继续猜测75,小于75,那么范围就缩小成了50-75,

继续猜测63,小于63,范围缩小到了50-63

这样下去,原本100个数字,最多只需要log2n 次即可查出数据

100的数据,只需要最多8次即可查出

php代码实现

随机抽取 1-100 的一个数字,猜测这个数字是多少?

<?php

//随机抽取1-100数字
$randNum = mt_rand(0,100);
echo "实际值为:{$randNum}\n";

function guess($randNum,$minNum,$maxNum,$guessNum=1){
    //二分查找,除以2
    $num = intval(($maxNum-$minNum)/2);
    //中间值不能直接比较,需要再加上最小值,例如50-100,(100-50)/2等于25,中间值是50+25等于75
    $guessValue = $num +$minNum;
    echo "猜测第{$guessNum}次:{$guessValue}\n";
    if ($guessValue==$randNum){
        return $randNum;
    }elseif ($guessValue>$randNum){
        //猜测值大于实际值
        return guess($randNum,$minNum,$guessValue,$guessNum+1);
    }elseif ($guessValue<$randNum){
        //猜测值小于实际值
        return guess($randNum,$guessValue,$maxNum,$guessNum+1);
    }
}

$num = guess($randNum,0,100);
echo "最终值:{$num}";

输出: