编程小知识之 range search

用户2615200

发布于 2021-09-10 10:49:19

50800

代码可运行

文章被收录于专栏：tkokof 的技术,小趣及杂念tkokof 的技术,小趣及杂念

运行总次数：0

代码可运行

本文简述了 range search 的一些知识

问题

所谓 range search,是指给定一些数值范围(range)和某一数值,我们来搜索该数值所属的数值范围,譬如我们给定以下的数值范围:

[0, 10] -> range 0
[11, 50] -> range 1
[51, 100] -> range 2

给定的数值为 32,那么我们可以搜索得到 32 所属的数值范围为: range 1.

实现

如果给定的数值范围比较少,我们直接遍历搜索就可以了,代码大概如下:

public int RangeSearch(int key)
{
    var count = rangeConfig.Length;
    for (int i = 0; i < count; ++i)
    {
        var config = rangeConfig[i];
        if (key >= config.Min && key <= config.Max)
        {
            return config.Value;
        }
    }

    return -1;
}

但是如果给定的数值范围较多时,遍历的时间消耗就比较大了,考虑到范围本身是有序的,我们很容易想到可以用二分搜索来优化:

public int RangeSearch(int key)
{
    int count = rangeConfig.Length;
    int l = 0;
    int r = count - 1;
    while (l <= r)
    {
        int m = l + (r - l) / 2;
        var config = rangeConfig[m];

        if (key >= config.Min && key <= config.Max)
        {
            return config.Value;
        }

        if (config.Max < key)
        {
            l = m + 1;
        }
        else
        {
            r = m - 1;
        }
    }

    return -1;
}

进阶

二分搜索其实已经比较快了,但是结合范围特性,我们还可以做的更好.

范围连续并且间隔相等

如果范围连续并且间隔相等,我们就可以对数值进行直接的范围映射:

假设范围的数值从 v 开始,并且间隔为 i,那么我们可以直接使用以下公式来进行映射范围: index=floor((value−v)/i)

代码如下:

public int RangeSearch(int key)
{
    int index = (key - v) / i;
    if (index >= 0 && index < rangeConfig.Length)
    {
        return rangeConfig[index].Value;
    }

    return -1;
}

数值所属范围集中

如果给定的数值范围很多,但实际数值所属的范围很集中,那么我们可以使用基于熵的方法来优化:

一种方法就是将范围按集中度进行排序,然后遍历搜索

public int RangeSearch(int key)
{
    // NOTE rangeConfig is ordered by aggregation degree
    var count = rangeConfig.Length;
    for (int i = 0; i < count; ++i)
    {
        var config = rangeConfig[i];
        if (key >= config.Min && key <= config.Max)
        {
            return config.Value;
        }
    }

    return -1;
}

另一种就是每次搜索都将搜索得到的范围前移:

public int RangeSearch(int key)
{
    var count = rangeConfig.Length;
    for (int i = 0; i < count; ++i)
    {
        var config = rangeConfig[i];
        if (key >= config.Min && key <= config.Max)
        {
            if (i > 0)
            {
                var pre = rangeConfig[i - 1];
                rangeConfig[i - 1] = rangeConfig[i];
                rangeConfig[i] = pre;
            }
            return config.Value;
        }
    }

    return -1;
}

SplayTree 很适合来做这类前置操作:

public int RangeSearch(int key)
{
    var node = splayTree.Find(key);
    if (node != null)
    {
        return node.Key.Value;
    }

    return -1;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021/04/09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度