PHP实现二分法查找

在一个有序表或数组中,查找一个元素是否存在,用二分查找的过程是:首先找出集合中间的那个元素,如果此元素比要查的元素大,就接着在较小的半个区域进行查找;反之,如果此元素比要查找的元素小,就在较大的那半个区域查找。在每个更小的数据集中重复这个查找过程,直到找到要查找的元素或者数据集不能再分割。PHP程序如下

经过两次笔试中的推导,终于将模糊记忆的二分法查找的概念用PHP代码实现,算是又掌握了一种算法。happy~

<?php
    function bin_search($arr,$search){
        $low = 0;
        $high = count($arr)-1;
        while( $low <= $high){
            $mid = intval(($low + $high)/2);
            if($arr[$mid] == $search){
                return $mid;
            }else if( $arr[$mid] > $search ){
                $high = $mid-1;
            }else{
                $low = $mid+1;
            }
        }
        return "can't search the '$search' in array!";
    }

    $test_arr = array(1,3,5,6,8,9);
    //$result = bin_search($test_arr , 1);
    //$result = bin_search($test_arr , 9);
    $result = bin_search($test_arr , 6);
    //$result = bin_search($test_arr , 'x');
    echo $result;
?>

 

2 thoughts on “PHP实现二分法查找”

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>