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

Question

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

0
1500
5000
9348
89234
109280
109281
109283
150000

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

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

Хочется, чтобы я не спал через класс алгоритмов.

Answer 1

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

Вот фактический алгоритм, который продолжает делить данные поиска на 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 2

Я думаю Алгоритм "разделяй и властвуй" - лучший вариант.

Answer 3

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

Взгляните здесь . (образец НЕ работает с IE)

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

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

Bye

Answer 4

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