查看我的数字是否在范围数组中的最佳算法是什么？

Question

我在PHP中有一个包含范围的二维数组.例如:

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

等等

这是一个很长的清单.现在我想看看用户给出的数字是否在范围内.例如,数字130,4200,52272933在我的范围内,但数字1,5,500不在.

当然,我可以统计所有索引,看看我的数字是否大于第一项,小于第二项.但有没有更快的算法或使用PHP功能更有效的方式？

后来补充道

它已分类.它实际上是用ip2long()创建的数字,显示一个国家的所有IP.我刚刚为它写了一个代码:

$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;}
}

在这种情况下,数字2,8,22和200在范围内.但不是数字1,11,300

Answer 1

您可以通过实现二进制搜索算法来加快速度。因此，您不必查看每个范围。然后你可以用它in_array来检查数字是否在数组中。

我不确定我是否理解正确，你的数组是否真的像这样：

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

如果是这样，有什么意义？为什么不只是拥有？

array(125, 3957);

其中包含所有必要的信息。

Answer 2

将范围放在从低到高排序的平面数组中，如下所示：

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

然后进行二进制搜索，以确定应在该数组的哪个索引处插入相关数字。如果插入索引为偶数，则该数字不在任何子范围内。如果插入索引为奇数，则该数字落在范围之一内。

例子：

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