在一维空间中最适合用于最近邻的数据结构

Question

我有一个值列表（一维），想知道查找最接近查询值的最佳数据结构/算法。在这里找到的大多数解决方案（全部？）都是针对2个或更多维度的问题。有人能为我提出适合我的情况的方法吗？

我的直觉告诉我对数据进行排序，然后以某种方式使用二分查找。顺便说一下，任何需要构建或插入时间的树都没有限制，因此可能有人能够建议比简单排序列表更好的树。

- Muhammad Alkarouri

---

我认为将BST与二分搜索结合使用非常完美。 - Dave O.

Answer 1

如果您需要比O(log(n))更快的东西，可以使用van Emde Boas Tree，这可以轻松地通过排序数组或二叉搜索树获得。vEB树为您提供了O(log(log(n)))来搜索两侧最接近的元素。

- mathmike

---

与排序数组相比，vEB树是一个复杂的空间占用者。除非点非常密集，否则内存层次结构的影响很可能会抵消O(log n)和O(log log n)之间的理论差别，甚至更多。 - user382751

这很令人印象深刻。就大量线性数据而言，我认为这是目前为止最好的理论答案，因此我接受了它。不过实际上，我将使用排序列表/二分查找，这对我的目的应该足够了。 - Muhammad Alkarouri

Answer 2

如果插入时间不重要，那么在已排序的数组上进行二分查找是实现O(log N)查询时间的最简单方法。每次添加一个项目时都要对所有内容进行排序。对于每个查询，执行二分查找。如果找到匹配项，则返回它。否则，二分查找应该返回该项应该插入的索引。使用此索引检查两个相邻的项目，并确定哪一个更接近查询点。

我想有O(1)时间的解决方案。我将尝试想出一种不涉及太多内存使用的解决方案...

- Eyal Schneider

---

那应该很有趣。我不知道你如何在不考虑数据集大小的情况下找到最近的邻居，如果你有任何解决方案，请在这里添加，尽管目前更多是学术上的好奇心。 - Muhammad Alkarouri

@Muhammad：这是时间复杂度和空间复杂度之间的权衡。假设您没有空间问题（或值的范围不是很大），那么您可以简单地创建一个巨大的数组，其中包含在位置k上最接近查询值k的点。这具有查询时间复杂度O(1)和空间复杂度O(max-min)。我不确定如何改进空间复杂度，然而... - Eyal Schneider

很好的想法。所以这看起来像是查找最近函数的查找表实现。问题在于，我能想到的任何哈希都会将其转换为O(log n)的东西。 - Muhammad Alkarouri

Answer 3

对列表进行排序并使用二分查找来查找您要查找的元素，然后比较左右邻居。您可以使用具有O(1)访问的数组。

类似于：

int nearest(int[] list, int element) {

    sort(list);
    int idx = binarySearch(element, list);

    // make sure you are accessing elements that exist
    min = (element - list[idx-1] <= list[idx+1] - element) ? idx-1 : idx+1;

    return list[min];
}

这是O(n log n)的时间复杂度，如果您要执行许多查找操作，则会摊销。

编辑：为此，您必须将排序移出此方法。

- quantumSoup

---

首先，我仍然不明白min函数如何返回正确的项。您甚至没有与查询点进行比较。其次，摊销成本似乎并没有改善任何事情...在执行查询时，您不应该对列表进行排序。只有在修改点集合时才应该这样做。 - Eyal Schneider

实际上，如果将排序移出二分查找，时间复杂度应该是O(log n)。 - Muhammad Alkarouri

Answer 4

正如您已经提到的，最快、最简单的方法应该是对数据进行排序，然后查找数据点的左右邻居。

- swegi

Answer 5

使用OCaml的Set：

module S = Set.Make(struct type t = int let compare = compare end)

let nearest xs y =
  let a, yisin, b = S.split y xs in
  if yisin then y
  else
      let amax, bmin = S.max_elt a, S.min_elt b in
      if abs (amax - y) < abs (bmin - y) then amax else bmin

顺便提一下，您可能会喜欢我从OCaml for Scientists和The F#.NET Journal文章中提取的nth-nearest neighbor sample以及遍历网络：第n近邻居。

- J D