php实现简单的二分查找

<?php
// 待查找区间
$arr = [1, 3, 7, 9, 11, 57, 63,55, 99];
// 非递归查找57所在的位置
$find_key = binary_search_recursion($arr,399,0,count($arr));
echo('位置是'.$find_key).PHP_EOL;
echo($arr[$find_key]);


function binary_search_recursion(&$arr, $number, $lower, $high) {
    // 以$a,区间的中间点作为参照点比较
    $middle = intval(($lower + $high) / 2);
    // 最低点比最高点大就退出
    if ($lower > $high) {
        return -1;
    }
    if ($number > $arr[$middle]) {
        // 查找数比参照点大，舍去左边继续查找
        return binary_search_recursion($arr, $number, $middle + 1, $high);
    } elseif ($number < $arr[$middle]) {
        // 查找数比参照点小，舍去右边继续查找
        return binary_search_recursion($arr, $number, $lower, $middle - 1);
    } else {
        return $middle;
    }
}