<分区>
我想知道是否有可能在已排序的 List 中为列表中不的元素找到最接近的元素。
例如，如果我们有值 [1,3,6,7] 并且我们正在寻找最接近 4 的元素，它应该返回 3，因为 3 是数组中最大的数字，它小于 4 .
我希望这是有道理的，因为英语不是我的母语。
<分区>
我想知道是否有可能在已排序的 List 中为列表中不的元素找到最接近的元素。
例如，如果我们有值 [1,3,6,7] 并且我们正在寻找最接近 4 的元素，它应该返回 3，因为 3 是数组中最大的数字，它小于 4 .
我希望这是有道理的，因为英语不是我的母语。
最佳答案
因为集合是排序的，所以可以在 O( log n ) 中进行修改后的二分查找:
public static int search(int value, int[] a) {
if(value < a[0]) {
return a[0];
}
if(value > a[a.length-1]) {
return a[a.length-1];
}
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
int mid = (hi + lo) / 2;
if (value < a[mid]) {
hi = mid - 1;
} else if (value > a[mid]) {
lo = mid + 1;
} else {
return a[mid];
}
}
// lo == hi + 1
return (a[lo] - value) < (value - a[hi]) ? a[lo] : a[hi];
}
由于上面的大部分代码都是二进制搜索，您可以利用 binarySearch(...)在 std 库中提供并检查 插入点 的值:
public static int usingBinarySearch(int value, int[] a) {
if (value <= a[0]) { return a[0]; }
if (value >= a[a.length - 1]) { return a[a.length - 1]; }
int result = Arrays.binarySearch(a, value);
if (result >= 0) { return a[result]; }
int insertionPoint = -result - 1;
return (a[insertionPoint] - value) < (value - a[insertionPoint - 1]) ?
a[insertionPoint] : a[insertionPoint - 1];
}
关于java - 在排序列表中找到最近/最接近的值，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30245166/