Найти ближайшее значение в векторе с бинарным поиском

Ответ 1

Вы можете использовать data.table для выполнения двоичного поиска:

dt = data.table(w, val = w) # you'll see why val is needed in a sec
setattr(dt, "sorted", "w")  # let data.table know that w is sorted

Обратите внимание, что если столбец w еще не отсортирован, вам придется использовать setkey(dt, w) вместо setattr(.).

# binary search and "roll" to the nearest neighbour
dt[J(x), roll = "nearest"]
#     w val
#1: 4.5   4

В финальном выражении столбец val будет искать вас.

# or to get the index as Josh points out
# (and then you don't need the val column):
dt[J(x), .I, roll = "nearest", by = .EACHI]
#     w .I
#1: 4.5  3

Ответ 2

R>findInterval(4.5, c(1,2,4,5,6))
[1] 3

будет делать это с соотношением цены-прав (ближе всего, не переходя).

Ответ 3

Чтобы сделать это на символьных векторах, Мартин Морган предложил эту функцию в R-help:

bsearch7 <-
     function(val, tab, L=1L, H=length(tab))
{
     b <- cbind(L=rep(L, length(val)), H=rep(H, length(val)))
     i0 <- seq_along(val)
     repeat {
         updt <- M <- b[i0,"L"] + (b[i0,"H"] - b[i0,"L"]) %/% 2L
         tabM <- tab[M]
         val0 <- val[i0]
         i <- tabM < val0
         updt[i] <- M[i] + 1L
         i <- tabM > val0
         updt[i] <- M[i] - 1L
         b[i0 + i * length(val)] <- updt
         i0 <- which(b[i0, "H"] >= b[i0, "L"])
         if (!length(i0)) break;
     }
     b[,"L"] - 1L
} 

Ответ 4

x = 4.5
w = c(1,2,4,6,7)

closestLoc = which(min(abs(w-x)))
closestVal = w[which(min(abs(w-x)))]

# On my phone- please pardon typos

Если ваш вектор длинный, попробуйте двухэтапный подход:

x = 4.5
w = c(1,2,4,6,7)

sdev = sapply(w,function(v,x) abs(v-x), x = x)
closestLoc = which(min(sdev))

для сумасшедших длинных векторов (миллионы строк!, предупреждение - это будет на самом деле медленнее для данных, которые не очень, очень и очень большие).

require(doMC)
registerDoMC()

closestLoc = which(min(foreach(i = w) %dopar% {
   abs(i-x)
}))

Этот пример - просто дать вам базовую идею использования параллельной обработки при наличии огромных данных. Заметьте, я не рекомендую использовать его для простых и быстрых функций, таких как abs().

Ответ 5

Вы всегда можете реализовать собственный алгоритм бинарного поиска, чтобы найти ближайшее значение. В качестве альтернативы вы можете использовать стандартную реализацию libc bsearch(). Вы также можете использовать другие реализации бинарного поиска, но это не меняет того факта, что вы должны тщательно реализовать функцию сравнения, чтобы найти ближайший элемент в массиве. Проблема со стандартной реализацией бинарного поиска заключается в том, что она предназначена для точного сравнения. Это означает, что ваша импровизированная функция сравнения должна выполнять некоторую оценку, чтобы выяснить, достаточно ли элемента в массиве. Чтобы достичь этого, функция сравнения должна осознавать другие элементы в массиве, особенно следующие аспекты:

• положение текущего элемента (тот, который сравнивается с ключ).
• расстояние с ключом и как он сравнивается с соседями (предыдущий или следующий элемент).

Чтобы предоставить дополнительные знания в функции сравнения, ключ должен быть упакован с дополнительной информацией (а не только значением ключа). Как только функция сравнения узнает об этих аспектах, она может выяснить, является ли сам элемент ближайшим. Когда он знает, что он ближайший, он возвращает "match".

Следующий код C находит ближайшее значение.

#include <stdio.h>
#include <stdlib.h>

struct key {
        int key_val;
        int *array_head;
        int array_size;
};

int compar(const void *k, const void *e) {
        struct key *key = (struct key*)k;
        int *elem = (int*)e;
        int *arr_first = key->array_head;
        int *arr_last = key->array_head + key->array_size -1;
        int kv = key->key_val;
        int dist_left;
        int dist_right;

        if (kv == *elem) {
                /* easy case: if both same, got to be closest */
                return 0;
        } else if (key->array_size == 1) {
                /* easy case: only element got to be closest */
                return 0;
        } else if (elem == arr_first) {
                /* element is the first in array */
                if (kv < *elem) {
                        /* if keyval is less the first element then
                         * first elem is closest.
                         */
                        return 0;
                } else {
                        /* check distance between first and 2nd elem.
                         * if distance with first elem is smaller, it is closest.
                         */
                        dist_left = kv - *elem;
                        dist_right = *(elem+1) - kv;
                        return (dist_left <= dist_right) ? 0:1;
                }
        } else if (elem == arr_last) {
                /* element is the last in array */
                if (kv > *elem) {
                        /* if keyval is larger than the last element then
                         * last elem is closest.
                         */
                        return 0;
                } else {
                        /* check distance between last and last-but-one.
                         * if distance with last elem is smaller, it is closest.
                         */
                        dist_left = kv - *(elem-1);
                        dist_right = *elem - kv;
                        return (dist_right <= dist_left) ? 0:-1;
                }
        }

        /* condition for remaining cases (other cases are handled already):
         * - elem is neither first or last in the array
         * - array has atleast three elements.
         */

        if (kv < *elem) {
                /* keyval is smaller than elem */

                if (kv <= *(elem -1)) {
                        /* keyval is smaller than previous (of "elem") too.
                         * hence, elem cannot be closest.
                         */
                        return -1;
                } else {
                        /* check distance between elem and elem-prev.
                         * if distance with elem is smaller, it is closest.
                         */
                        dist_left = kv - *(elem -1);
                        dist_right = *elem - kv;
                        return (dist_right <= dist_left) ? 0:-1;
                }
        }

        /* remaining case: (keyval > *elem) */

        if (kv >= *(elem+1)) {
                /* keyval is larger than next (of "elem") too.
                 * hence, elem cannot be closest.
                 */
                return 1;
        }

        /* check distance between elem and elem-next.
         * if distance with elem is smaller, it is closest.
         */
        dist_right = *(elem+1) - kv;
        dist_left = kv - *elem;
        return (dist_left <= dist_right) ? 0:1;
}


int main(int argc, char **argv) {
        int arr[] = {10, 20, 30, 40, 50, 60, 70};
        int *found;
        struct key k;

        if (argc < 2) {
                return 1;
        }

        k.key_val = atoi(argv[1]);
        k.array_head = arr;
        k.array_size = sizeof(arr)/sizeof(int);

        found = (int*)bsearch(&k, arr, sizeof(arr)/sizeof(int), sizeof(int),
                compar);

        if(found) {
                printf("found closest: %d\n", *found);
        } else {
                printf("closest not found. absurd! \n");
        }

        return 0;
}

Излишне говорить, что bsearch() в приведенном выше примере никогда не должен прерываться (если размер массива не равен нулю).

Если вы реализуете свой собственный бинарный поиск, по сути, вам нужно встроить такую ​​же логику сравнения в основную часть двоичного кода поиска (вместо того, чтобы иметь эту логику в сравнении функции в приведенном выше примере).

Ответ 6

NearestValueSearch = function(x, w){
  ## A simple binary search algo
  ## Assume the w vector is sorted so we can use binary search
  left = 1
  right = length(w)
  while(right - left > 1){
    middle = floor((left + right) / 2)
    if(x < w[middle]){
      right = middle
    }
    else{
      left = middle
    }
  }
  if(abs(x - w[right]) < abs(x - w[left])){
    return(right)
  }
  else{
    return(left)
  }
}


x = 4.5
w = c(1,2,4,6,7)
NearestValueSearch(x, w) # return 3