编程小知识之 range search

迈不过友情╰ 2022-11-17 13:51 196阅读 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 v v 开始,并且间隔为  i i i,那么我们可以直接使用以下公式来进行映射范围:

i n d e x = f l o o r ( ( v a l u e − v ) / i ) index = floor((value - 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;
    }

[SplayTree]: https://en.wikipedia.org/wiki/Splay_tree