PHP实现二分查找算法

本篇笔记记录了递归和循环两种方式实现二分查找算法,同时针对关联数组也做了测试。

二分查找又称折半查找,二分查找算法要求数据必须是有序的,以下是php实现二分查找算法的代码。
一:递归方式

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];

$target = 73;

$low = 0;

$high = count($array)-1;

function bin_search($array, $low, $high, $target){
    if ( $low <= $high){
        var_dump($low, $high);echo "\n";
        $mid =  intval(($low+$high)/2 );
        if ($array[$mid] ==  $target){
            return true;
        }elseif ( $target < $array[$mid]){
            return  bin_search($array, $low,  $mid-1, $target);
        }else{
            return  bin_search($array, $mid+ 1, $high, $target);
        }
    }
    return false;
}

$find = bin_search($array, $low, $high, $target);

var_dump($find);

执行结果

int(0)
int(25)

int(13)
int(25)

int(20)
int(25)

int(20)
int(21)

bool(true)

我们看到,经过4次二分查找,查找区间不断折半,最终找到了$target。
二:循环方式

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];

$target = 73;

function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$mid] == $target){
                $find = true;
                break;
            } elseif ($array[$mid] < $target){
                $low = $mid+1;
            } elseif ($array[$mid] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);

var_dump($find);

执行结果

int(0)
int(25)

int(13)
int(25)

int(20)
int(25)

int(20)
int(21)

bool(true)

我们看到,两种方式过程和结果相同。下面我们来测试下针对关联数组的二分查找算法:

$array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38];

$target = 19;

function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $key_map = array_keys($array);
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$key_map[$mid]] == $target){
                $find = true;
                break;
            } elseif ($array[$key_map[$mid]] < $target){
                $low = $mid+1;
            } elseif ($array[$key_map[$mid]] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);

var_dump($find);

执行结果

int(0)
int(8)

int(5)
int(8)

bool(true)

两次二分查找,找到了$target,针对关联数组,我们使用了php的array_keys函数获得这个关联有序数组的key,通过key间接比对$target和$array的值。