## 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
``````