algorithm - 在一组整数中寻找最近的元素

Question

我有以下问题需要解决:

给定构成集合 S 的 N 个整数和另一个整数 A(不一定与给定的 N 个整数中的任何一个相同)，从集合 S 中找到最接近整数 A 的整数。

我首先认为这是一个 NNS(最近邻搜索)问题，但在 NNS 中，整数 A 也必须来自集合 S，在我的例子中它不一定是。

然后我想到将 S 中的每个整数放入二叉搜索树中，并搜索其中一个子项小于查询且父项大于查询的第一次出现，但我不知道这是否可行。

我应该使用哪种数据结构？谢谢。

编辑:忘了说我需要它比 O(n) 更好，O(logn) 就足够了。因此我不能使用线性搜索。

Answer 1

您的问题是在已排序数组/列表中二进制搜索 的典型输入。唯一的困难是了解四种 情况(参见我的 C# 实现)。二分查找通常可以作为标准库的一部分找到，在 C# 中

https://msdn.microsoft.com/en-us/library/y15ef976(v=vs.110).aspx

private static int Closest(int[] S, int A) {
  int index = Array.BinarySearch(S, A);

  if (index >= 0)
    return S[index];        // exact match, A in S
  else if (index == -1)
    return S[0];            // A is less than any item in S
  else if (index < -S.Length)
    return S[S.Length - 1]; // A is greater than any item in S
  else {                    // A is in [left..right] range
    // C# specific range encoding; consult your languages/library manual   
    int left = ~index - 1;
    int right = ~index;

    if (Math.Abs(S[left] - A) < Math.Abs(S[right] - A))
      return S[left];
    else
      return S[right];
  }

测试:

  int[] array = new[] { 10, 20, 30, 40, 50 };

  // 10
  Console.Write(Closest(array, 11));
  // 20
  Console.Write(Closest(array, 19));
  // 10
  Console.Write(Closest(array, 4));
  // 50
  Console.Write(Closest(array, 400));
  // 30
  Console.Write(Closest(array, 30));