区间查找算法

  1. 分析
  2. 性能考虑
  3. 可行性分析
  4. 搜索实现
    1. 伪代码
    2. 类型说明
    3. 抽象成策略
    4. 具体实现
  5. 处理区间,去除重叠部分
    1. 伪代码
    2. 代码实现

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

分析

需要满足以下几个条件:

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

性能考虑

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

可行性分析

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

搜索实现

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

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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)类型供算法使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
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),做到与具体实现分离:

1
2
3
4
5
6
7
8
9
package com.moss.arithmetic;
/**
* 区间搜索策略接口
*/
public interface IRagionStrategy {

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

具体实现

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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);
}

}
}
}


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 jaytp@qq.com

💰

×

Help us with donation