Лучшая структура данных для ближайшего соседа в 1 размере

Если время вставки не имеет значения, тогда двоичный поиск в отсортированном массиве - это самый простой способ добиться времени запроса O (log N). Каждый раз, когда добавляется элемент, сортируйте все. Для каждого запроса выполните двоичный поиск. Если совпадение найдено, верните его. В противном случае двоичный поиск должен вернуть индекс элемента, в который он должен был быть вставлен. Используйте этот индекс, чтобы проверить два соседних элемента и определить, какой из них ближе к точке запроса.

Я полагаю, что есть решения с временем O (1). Я постараюсь придумать такой, который не требует слишком большого использования памяти ...

Отсортируйте список и используйте двоичный поиск, чтобы найти элемент, который вы ищете, затем сравните своих левых и правых соседей. Вы можете использовать массив с доступом 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), которое будет амортизировано, если вы собираетесь выполнить много поисков.

РЕДАКТИРОВАТЬ: Для этого вам нужно переместить сортировку из этого метода

Как вы уже упоминали, самым быстрым и простым способом должна быть сортировка данных с последующим поиском левого и правого соседа точки данных.

Использование OCaml's 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

Кстати, вы можете оценить мой образец nth-ближайшего соседа из OCaml for Scientists и The F #. NET Journal статья Обход сети: n-е ближайшие соседи .