Ищете эффективный алгоритм для нахождения ближайшего целого числа в списке целых чисел

Question

Вот ситуация. У меня есть отсортированный список целых чисел, представляющих события, которые нужно уволить на определенную миллисекунду. Этот список может выглядеть следующим образом:

0 
1500 
5000 
9348 
89234 
109280 
109281 
109283 
150000 

Я тогда playhead, который обычно движется вперед каждые 100 мс, но может случайным образом искать и кустарниковые вперед и назад, а также. Этот проигрыватель не гарантирует, что он будет кратным 100, но может быть перекрыт до нескольких, без каких-либо реальных проблем.

Мой вызов состоит в том, чтобы иметь возможность эффективно находить ближайший элемент в списке, который меньше или равен текущей точке воспроизведения. Средняя длина списка составляет от 300 до 1500 элементов. Я могу легко оптимизировать форвард с заданными интервалами, но случайный поиск немного сложнее.

Заставляет меня пожелать, чтобы я спал по классу алгоритмов.

Answer 1

думаю Divide and conquer algorithm - лучший костюм.

Answer 2

Похоже, вы хотите изменить бинарный поиск. Поскольку список отсортирован по порядку, бинарный поиск значительно улучшит эффективность поиска по линейному поиску, и если вы ничего не знаете об интервалах элементов в массиве, вы не сможете сделать намного лучше, чем двоичный поиск. Бинарный поиск должен быть слегка изменен, потому что вы не ищете равенства, а что-то вроде как близко, не переходя.

Вот фактический алгоритм, который сохраняет разделив данные поиска в 1/2 (переход с верхней половины или нижней половине каждый раз на основе сравнения со значением теста), пока она не сводится только один элемент:

var testData = [0,1500,5000,9348,89234,109280,109281,109283,150000]; 

function findNearest(data, val) { 
    if (!data || !data.length) { 
     return(null); 
    } 
    var lowest = 0, mid; 
    var highest = data.length - 1; 
    while (true) {  
     if (lowest == highest) { 
      return(lowest); 
     } 
     mid = Math.ceil(((highest - lowest)/2) + lowest); 
     if (data[mid] == val) { 
      return(mid); 
     } 
     else if (data[mid] < val) { 
      lowest = mid; 
     } else { 
      highest = Math.max(lowest, mid - 1); 
     } 
    } 
} 

и, рабочая программа испытаний: http://jsfiddle.net/jfriend00/rWk2X/

Примечание: этот код предполагает, что все значения в массиве в отсортированном порядке, и массив не пуст.

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

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

Answer 3

Поскольку это отсортированный список, используйте двоичный поиск. Вы можете сделать лучше, но тогда вам нужно сделать дополнительные предположения (например, вы должны предполагать даже распределение чисел, что, на мой взгляд, не так). Вы можете прочитать об этом здесь: http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 4

Я столкнулся с этой проблемой некоторое время назад и провел несколько сравнений времени выполнения.

Посмотрите here. (образец НЕ работает с IE)

Четвертая реализация, похоже, действительно правильна по сравнению с немым двоичным поиском.

Надеюсь, это поможет.

Bye