find smallest number greater than given number out of a sorted list

20 May 2014

Give out a sort list:

60, 80, 100, 120, 160, 320, 480, 640, 720, 1080

Find out the smallest number but greater than given number. For example:

10 => 80
60 => 80
100 => 100
140 => 160
200 => 320
1080 => 1080
1800 => 1080

Simply, we can use for a for loop to archive this, and its complexity is O(n);

Here I use a binary search, whose complexity will be O(logn):

<?php
function bin_search($map, $num)
{
    $l = 0;
    $h = count($map) - 1;

    $f = $num;
    while ($h > $l)
    {
        $m = floor(($h + $l) / 2);
        if ($map[$m] >= $num)
        {
            $h = $m;
        }
        else
        {
            $l = $m;
        }
        if ($h == $l + 1)
        {
            break;
        }
    }
    return $map[$h];
}
function test($num)
{
    $map = array(
        60,
        80,
        100,
        120,
        160,
        320,
        480,
        640,
        720,
        1080,
    );

    printf("%s => %s\n", $num, bin_search($map, $num));
}
test(10);
test(60);
test(100);
test(140);
test(200);
test(1080);
test(1800);

The output:

[huqiu@101 ~]$ php test.php
10 => 80
60 => 80
100 => 100
140 => 160
200 => 320
1080 => 1080
1800 => 1080