时间戳

首页 > 解决方案 > O(1) 查找范围

algorithm - O(1) 查找范围

问题描述

有没有办法快速查找一个值的对应范围？

例如：我有一堆预先指定的范围：[0,50)、[50, 100)、[100,200)等。我想检查十进制值属于哪个预先指定的范围：

我知道，如果我只是检查特定的离散值，那么O(1)通过使用带有键/值的数据结构来实现它非常简单：

function(value) {
    return obj[value];
}

但是，如果我想检查一个值属于哪个范围，那么我看不到不遍历范围的方法，这使得它O(n)：

function(value) {
    if (value < a) {
        return 'a';
    } else if (value < b) {
        return 'b';
    } else if (value < c) {
        return 'c';
    }
}

如果我的输入是整数或其他离散值，那么我仍然可以使用数据结构方法，但如果我的输入是小数，是否有办法更快地做到这一点？

我尝试的一种方法是使用该函数x/abs(x)创建一个阶跃函数，然后将多个这些函数组合在一起的事实。例如：

x/abs(x) + (x-50)/(abs(x-50)) + (x-100)/(abs(x-100)) + (x-200)/(abs(x-200))

这会将所有十进制值映射到离散输出，然后您只需应用对象键/值查找。

但是计算这个所需的操作数仍然是O(n).

标签： algorithmsearchlookup

解决方案

由于您提到您的范围是连续的，因此这里有一个 O(1) 算法，用于查找特定值所属的范围。它的缺点是它可能需要大量内存来处理非常大的范围和非常小的范围。

  1. 选择一个合适的常数s <= 1。越大s，算法越快，但它使用的内存越多。

  2. 创建一个数组数组T。对于每个i有限制的范围lo, hi，追加i到T[j]所有s*lo <= j < s*hi。现在预处理完成了。

  3. 查找值x时，请查看T[floor(s*x)]和T[ceil(s*x)]。在这两个数组之一中，您会发现该范围x属于其中。

例如，如果我选择，我可以为范围s = 1/50创建以下查找表。事实上，由于每个数组的大小为 1，我可以直接构造一个数组而不是数组数组：T[0,50), [50, 100), [100,200)

[0, 1, 2, 2]

查找 x = 141，我们查看T[floor(141/50)] = T[2] = 2并发现它确实ranges[2]包含我们感兴趣的范围。

对于连续的整数范围，我们发现这s = 1/gcd(lo1, lo2, lo3, ...)是最节省内存的选择，s可以保持最快的查找时间，每个条目只有 1 个范围T。

推荐阅读