这是一种修改后的二分搜索,它返回排序数组列表中与给定值最接近的元素。我如何调整它,以便它可以返回 2 个最近的前一个元素和 2 个最近的下一个元素?
private static Long search(long value, ArrayList<Long> a) {
if(value < a.get(0)) {
return a.get(0);
}
if(value > a.get(a.size()-1)) {
return a.get(a.size()-1);
}
int lo = 0;
int hi = a.size() - 1;
while (lo <= hi) {
int mid = (hi + lo) / 2;
if (value < a.get(mid)) {
hi = mid - 1;
} else if (value > a.get(mid)) {
lo = mid + 1;
} else {
return a.get(mid);
}
}
return (a.get(lo) - value) < (value - a.get(hi)) ? a.get(lo) : a.get(hi);
}
例如,让我们考虑我的数组列表由以下元素组成:
[101、201、301、401、501、601、701、801、901、1001]
我得到的值是 730。我希望搜索返回一个由 4 个元素组成的数组,其中包含 601、701 作为前一个值,801 和 901 作为下一个值。
最佳答案
此代码使用一种非常简单的方法,根据 lo
、hi
和 mid
值之间的差异将元素添加到结果列表中。
在边缘情况下,返回的元素数量可能小于 4。例如,如果左侧或右侧没有元素(由于列表边界),则返回的列表大小可以是 2 或 3取决于最接近值的位置。
如果这是您想要的,那么这是代码:
private static List<Long> search(long value, List<Long> a) {
if (a.size() < 3) return new ArrayList<>(a);
List<Long> result = new ArrayList<>();
if (value < a.get(0)) {
result.add(a.get(0));
result.add(a.get(1));
return result;
}
if (value > a.get(a.size() - 1)) {
result.add(a.get(a.size() - 2));
result.add(a.get(a.size() - 1));
return result;
}
int lo = 0;
int hi = a.size() - 1;
int match = -1;
while (lo <= hi) {
int mid = (hi + lo) / 2;
if (value < a.get(mid)) {
hi = mid - 1;
} else if (value > a.get(mid)) {
lo = mid + 1;
} else {
match = mid;
break;
}
}
if (match >= 0) {
if (match > 1) result.add(a.get(match - 2));
if (match > 0) result.add(a.get(match - 1));
if (match < a.size() - 1) result.add(a.get(match + 1));
if (match < a.size() - 2) result.add(a.get(match + 2));
} else if (a.get(lo) < value) {
result.add(a.get(hi));
result.add(a.get(lo));
if (lo < a.size() - 1) result.add(a.get(lo + 1));
if (lo < a.size() - 2) result.add(a.get(lo + 2));
} else if (a.get(hi) > value) {
if (hi > 1) result.add(a.get(hi - 2));
if (hi > 0) result.add(a.get(hi - 1));
result.add(a.get(hi));
result.add(a.get(lo));
} else {
if (hi > 0) result.add(a.get(hi - 1));
result.add(a.get(hi));
result.add(a.get(lo));
if (lo < a.size() - 1) result.add(a.get(lo + 1));
}
return result;
}
关于java - 在排序数组列表中查找 2 个最近的前一个值和 2 个最近的下一个值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49099605/