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

二分查找递归与非递归实现

程序员文章站 2024-03-19 15:37:40
...

用PHP完成二分查找递归与非递归实现

<?php
    //非递归实现二分查找
    function binarySearch($arr, $target) {
        $low = 0;
        $high = count($arr) - 1;
        while($low <= $high)
        {
            $mid = floor(($low+$high)/2);
            if($target < $arr[$mid])
                $high = $mid - 1;
            else if($target > $arr[$mid])
                $low = $mid + 1;
            else
            {
                return $mid;
            }
        }
        return '没有找到';
    }
    //递归实现二分查找
    function binSearch($arr,$start,$end,$target)
    {
        //$end = count($arr) - 1;
        $mid = floor( ($start + $end) / 2 );
        if($start > $end)
            return '没有找到';
        else if($target > $arr[$mid])
            return binSearch($arr,$mid+1,$end,$target);
        else if($target < $arr[$mid])
            return binSearch($arr,$start,$mid-1,$target);
        else
            return $mid;
    }

    $myarr = [1,3,5,7,11];
    echo binarySearch($myarr,7);
    echo binarySearch($myarr,12);
    echo '<br/>';
    echo binSearch($myarr,0,count($myarr)-1,11);
    echo binSearch($myarr,0,count($myarr)-1,12);
?>
相关标签: php 二分查找