一个菜鸟驿站!

二分法查找多种写法

PHP 2021-05-09 浏览(2181) 评论(0)
- N +

文章目录 [+]

image.png

二分法简单原理

想要写出二分法查找的代码,首先要懂得二分法实现查找的原理。注:前提为有序的数组

  • 要知道中间位置就需要知道起始位置结束位置,然后取出中间位置的值来和我们的值做对比。

  • 如果中间值大于我们的给定值,说明我们的值在中间位置之前,此时需要再次二分,因为在中间之前,所以我们需要变的值是结束位置的值,此时结束位置的值应该是我们此时的中间位置。

  • 反之,如果中间值小于我们给定的值,那么说明给定值在中间位置之后,此时需要再次将后一部分的值进行二分,因为在中间值之后,所以我们需要改变的值是开始位置的值,此时开始位置的值应该是我们此时的中间位置,直到我们找到指定值。

  • 或者中间值等于最初的起始位置,或结束位置(此时说明给定值未找到)


php呈现方式1(递归)

function searchValue($array, $searchValue, $low = 0, $high = 0)
{
    //如果数组不为空,且最大值为初始值0
    if (count($array) && $high == 0) {
        $high = count($array) - 1 ;
    }

    //如果最小值<=最大值
    if ($low <= $high) {
        $mid = (int) (($low + $high) / 2);
        //查找的值等于中间值,那么直接返回该值在数组的位置
        if ($array[$mid] == $searchValue) {
            return $mid;
        }
        if ($searchValue > $array[$mid]) {
            //查找的值大于中间值,那么往后查找,最小值为当前值+1,最大值不变
            return searchValue($array, $searchValue, $mid + 1, $high);
        }else{
            //查找的值小于当前中间值,那么往前找,最小值不变,最大值为最小值-1
            return searchValue($array, $searchValue, $low, $mid - 1);
        }
    }
    //未找到,返回-1
    return -1;
}
$arr = [1,2,3,4,5,6,7,8,9,10];
echo searchValue($arr, 10);

php呈现方式2(while)

$arr = [1,2,3,4,5,6,7,8,9,10];

$searchValue = 0;
$min = 0;
$max = count($arr) - 1;
$mid = (int) (($min + $max) / 2);
while (true) {
    //如果最小值<=最大值
    if ($min <= $max) {
        //查找的值等于中间值,那么直接返回该值在数组的位置
        if ($arr[$mid] == $searchValue) {
            echo '位置:' . $mid;die;
        }

        if ($searchValue > $arr[$mid]) {
            //查找的值大于中间值,那么往后查找,最小值为当前值+1,最大值不变
            $min = $mid + 1;
        }else{
            //查找的值小于当前中间值,那么往前找,最小值不变,最大值为最小值-1
            $max = $mid - 1;
        }
        //重置中间值
        $mid = (int) (($min + $max) / 2);
    }else{
        echo '未找到';die;
    }
}


标签:
作者:猫巷

,

评论列表 (0)条评论

发表评论

召唤伊斯特瓦尔