Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the best algorithm to see if my number is in an array of ranges?

I have a 2 dimensional arrays in php containing the Ranges. for example:

From.........To
---------------
125..........3957
4000.........5500
5217628......52198281
52272128.....52273151
523030528....523229183  

and so on

and it is a very long list. now I want to see if a number given by user is in range. for example numbers 130, 4200, 52272933 are in my range but numbers 1, 5600 are not.

of course I can count all indexes and see if my number is bigger than first and smaller than second item. but is there a faster algorithm or a more efficient way of doing it using php function?

added later

It is sorted. it is actually numbers created with ip2long() showing all IPs of a country. I just wrote a code for it:

$ips[1] = array (2,20,100);
$ips[2] = array (10,30,200);
$n=11;// input ip
$count = count($ips);
for ($i = 0; $i <= $count; $i++) {
    if ($n>=$ips[1][$i]){
        if  ($n<=$ips[2][$i]){
            echo "$i found";
            break;
        }
    }else if($n<$ips[1][$i]){echo "not found";break;}
}

in this situation numbers 2,8,22,and 200 are in range. but not numbers 1,11,300

like image 957
Towhid Avatar asked Dec 10 '11 18:12

Towhid


2 Answers

Put the ranges in a flat array, sorted from lower to higher, like this:

a[0] = 125
a[1] = 3957
a[2] = 4000
a[3] = 5500
a[4] = 5217628
a[5] = 52198281
a[6] = 52272128
a[7] = 52273151
a[8] = 523030528
a[9] = 523229183

Then do a binary search to determine at what index of this array the number in question should be inserted. If the insertion index is even then the number is not in any sub-range. If the insertion index is odd, then the number falls inside one of the ranges.

Examples:

n = 20  inserts at index 0 ==> not in a range
n = 126 inserts at index 1 ==> within a range
n = 523030529 inserts at index 9 ==> within a range
like image 184
Miguel Avatar answered Nov 15 '22 15:11

Miguel


You can speed things up by implementing a binary search algorithm. Thus, you don't have to look at every range. Then you can use in_array to check if the number is in the array.

I'm not sure if I got you right, do your arrays really look like this:

array(125, 126, 127, ..., 3957);

If so, what's the point? Why not just have?

array(125, 3957);

That contains all the information necessary.

like image 28
middus Avatar answered Nov 15 '22 14:11

middus