区间查找算法

有一个需求，业务里需要判断一个数组的数值变化趋势，所以定义了一套门限，但是现在觉得这个门限太全局了，需要缩小范围， 最好一段一段的，趋势的判断也会改变原来的逻辑，每次获取门限的时候都带上数组的索引，因此需要设计一个算法，接受到一个 数组索引，可以快速查询出对应的门限区间，进而拿到该门限。

分析

需要满足以下几个条件：

  1. 区间有可能会重合，需要做区间的去重操作；
  2. 区间的查询速度一定要快，因为原始的数组非常大，每个数组元素都会访问一遍；

性能考虑

因为有可能分段会非常多，所以提升速度，选用二叉搜索来提升效率，但是有一点需要注意，二叉查询前必须要确保区间没有重叠， 这个可以最后做一下数据的预处理。

可行性分析

有序的区间序列有特点：当前区间的起始一定小于前一个区间的结束；因此如果给定一个值想知道在哪个区间，二分是可行的。

搜索实现

以下是保证区间没有重复后所实现的搜索方法。因为我的代码还没有用作实际的生产，所以只是定义接口进行测试.

伪代码

double value; // 给定的值
IRange wantedRange; // 结果区间
IRange[] range; // 区间端信息
int start=0, end=range.length; // 区间的默认始末

// 二分查找
while(start <= end)
{
	mid = (start + end) / 2; //折半

	if(value <= range[mid].start)
	{
  		end = mid - 1; 
  		continue; // 修正区间继续
	}

	if(value > range[mid].end)
	{
  		start = mid + 1;
  		continue; // 修正区间继续
	}

	wantedRange = range[mid]; // 找到了
	break;
}

类型说明

因为没有具体类型的设计，所以定义接口(IRagion.java)类型供算法使用:

package com.moss.arithmetic;

/**
 * 类型： 区域, 左开右闭
 */
public interface IRagion {

    /**
     * 获取区间起始
     *
     * @return 区间起始
     */
    double getStart();

    /**
     * 获取区间结束
     *
     * @return 区间结束
     */
    double getEnd();

    /**
     * 修正区间的起始
     *
     * @param start 新的区间起始
     */
    void setStart(double start);

    /**
     * 修正区间结束
     *
     * @param end 新的区间结束
     */
    void setEnd(double end);
}

抽象成策略

因为考虑到可能还会有更加完美的算法，所以搜素定义成策略接口(IRagionStrategy.java)，做到与具体实现分离:

package com.moss.arithmetic;
/**
 * 区间搜索策略接口
 */
public interface IRagionStrategy {

    /** 根据给定的值搜索所在的区间， 如果没有找到， 返回null */
    IRagion search(double value);
}

具体实现

目前我能想到的好方法还只是使用二叉来提高搜索效率RagionStrategy.java:

package com.moss.arithmetic;

import java.util.List;

/**
 * 分区查找策略
 */
public class RagionStrategy implements IRagionStrategy {

    /**
     * 保存分段信息
     */
    private List<IRagion> ragionList;

    /**
     * 当前的位置
     */
    private double value;

    /**
     * 入参务必要保证区间不能重合
     *
     * @param ragionList 区间列表
     */
    public RagionStrategy(List<IRagion> ragionList) {
        this.ragionList = ragionList;
    }

    /**
     * 搜索距离所在的区间
     *
     * @param value 输入的位置
     * @return 位置所处的区间， 如果找不到返回null
     */
    @Override
    public IRagion search(double value) {
        return binarySearch(value);
    }

    /**
     * 二分查找
     *
     * @param value 需要查询的值
     * @return 找到的值所在区间
     */
    private IRagion binarySearch(double value) {

        // 默认找不到区间
        IRagion ret = null;

        // 初始化区间的始末
        int start = 0;
        int end = ragionList.size() - 1;

        // 只要区间合法， 就会一直搜索
        while (start <= end) {

            // 取出中点计算
            int mid = (start + end) / 2;
            IRagion ragion = ragionList.get(mid);

            // 如果要找的值比区间起始还要小，则只有区间左边的才有可能是
            if (Double.compare(value, ragion.getStart()) <= 0) {
                end = mid - 1;
                continue;
            }

            // 如果要找的值比区间的结束还要大，则只有区间右边的才有可能是
            if (value > ragion.getEnd()) {
                start = mid + 1;
                continue;
            }

            // 如果改值落在区间内(start, end],则说明找到了
            ret = ragion;
            break;
        }

        return ret;
    }

}

处理区间，去除重叠部分

假定我们的规则是，区间重叠部分认为是无效的部分，那么处理区间的逻辑简化为修正区间的起始和结束。

伪代码

  1. 按照区间的起始位置排序, 这样区间至少起始是有序的；
  2. 如果区间存在重叠，那么一定是当前区间的结束位置要后于下一个区间的起始，则去除重复后, 当前区间的结束就是下个区间的开始，下个区间的开始就是当前区间的结束，相当于交换前后当前区间的结束和下一个区间的开始

代码实现

因为是数据的特殊预处理，所以用一个简单的适配器RagionAdapter.java:

package com.moss.arithmetic;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * 区间适配器，在进入算法前，对数据进行预处理
 */
public class RagionAdapter {

    /**
     * 区间比较，按照区间的起始位置比较
     */
    private class RagionComparator implements Comparator<IRagion> {

        @Override
        public int compare(IRagion o1, IRagion o2) {
            return Double.compare(o1.getStart(), o2.getStart());
        }

    }

    /**
     * 处理区间为后面的算法做准备，去除区间的重合部分
     *
     * @param ragionList 原始的区间列表
     */
    public void handleRagion(List<IRagion> ragionList) {

        if (ragionList == null) {
            return;
        }

        // 先排序区间
        Collections.sort(ragionList, new RagionComparator());

        for (int i = 0, end = ragionList.size() - 1; i < end; i++) {

            IRagion currentRagion = ragionList.get(i);
            IRagion nextRagion = ragionList.get(i + 1);

            double currentEnd = currentRagion.getEnd();
            double nextStart = nextRagion.getStart();

            // 如果发现区间重合，直接去掉重合部分
            if (nextStart > currentEnd) {
                currentRagion.setEnd(nextStart);
                nextRagion.setStart(currentEnd);
            }

        }
    }
}
Loading Disqus comments...
Table of Contents