区间查找算法
Created At :
Views 👀 :
有一个需求,业务里需要判断一个数组的数值变化趋势,所以定义了一套门限,但是现在觉得这个门限太全局了,需要缩小范围,
最好一段一段的,趋势的判断也会改变原来的逻辑,每次获取门限的时候都带上数组的索引,因此需要设计一个算法,接受到一个
数组索引,可以快速查询出对应的门限区间,进而拿到该门限。
分析
需要满足以下几个条件:
- 区间有可能会重合,需要做区间的去重操作;
- 区间的查询速度一定要快,因为原始的数组非常大,每个数组元素都会访问一遍;
性能考虑
因为有可能分段会非常多,所以提升速度,选用二叉搜索来提升效率,但是有一点需要注意,二叉查询前必须要确保区间没有重叠,
这个可以最后做一下数据的预处理。
可行性分析
有序的区间序列有特点:当前区间的起始一定小于前一个区间的结束;因此如果给定一个值想知道在哪个区间,二分是可行的。
搜索实现
以下是保证区间没有重复后所实现的搜索方法。因为我的代码还没有用作实际的生产,所以只是定义接口进行测试.
伪代码
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 {
double getStart();
double getEnd();
void setStart(double start);
void setEnd(double end); }
|
抽象成策略
因为考虑到可能还会有更加完美的算法,所以搜素定义成策略接口(IRagionStrategy.java
),做到与具体实现分离:
1 2 3 4 5 6 7 8 9
| package com.moss.arithmetic;
public interface IRagionStrategy {
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;
public RagionStrategy(List<IRagion> ragionList) { this.ragionList = ragionList; }
@Override public IRagion search(double value) { return binarySearch(value); }
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; }
ret = ragion; break; }
return ret; }
}
|
处理区间,去除重叠部分
假定我们的规则是,区间重叠部分认为是无效的部分,那么处理区间的逻辑简化为修正区间的起始和结束。
伪代码
- 按照区间的起始位置排序, 这样区间至少起始是有序的;
- 如果区间存在重叠,那么一定是当前区间的结束位置要后于下一个区间的起始,则去除重复后,
当前区间的结束就是下个区间的开始,下个区间的开始就是当前区间的结束,相当于交换前后当前区间的结束和下一个区间的开始
代码实现
因为是数据的特殊预处理,所以用一个简单的适配器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()); }
}
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