php

php 二分法

<?php
set_time_limit(1);

function binary_search($arr, $k)
{
    $len = count($arr);
    $min = 0;
    $max = $len - 1;
    while (true) {
        if ($min > $max) return -1;
        $index = intval(($min + $max) / 2);
        if ($k == $arr[$index]) return $index;

        if ($k > $arr[$index]) {
            $min = $index + 1;
        } else {
            $max = $index - 1;
        }
    }
}

function binary_search_recursive($arr, $k, $min = -1, $max = -1)
{
    if ($min == -1) {
        $len = count($arr);
        $min = 0;
        $max = $len - 1;
    }

    if ($min > $max) return -1;
    $index = intval(($min + $max) / 2);
    if ($k == $arr[$index]) return $index;

    if ($k > $arr[$index]) {
        $min = $index + 1;
    } else {
        $max = $index - 1;
    }
    return binary_search_recursive($arr, $k, $min, $max);
}

$arr = range(1, 100);
var_dump(binary_search($arr, $_GET['v']));
var_dump(binary_search_recursive($arr, $_GET['v']));

发表评论