Привет,

Есть такая задачка:

Дан массив целых чисел a.
Размер массива n   0 < n <1kk
Значение элемента массива i 0 < i <1kk

Над данным массивом многократно осуществляется поиск самого близкого элемента i к заданной позиции. На каждом шаге поиска позиция поиска строго увеличивается. Количество шагов поисков < n

Пример:


Моя реализация тривиальная. Для каждого элемента мас. строится список позиций:
1: 0, 3, 6
2: 4, 7
3: 1
4: 2,5

На этапе поиска берется список позиций элемента и бинарным поиском находим позицию.

Есть идеи как можно ускорить такой поиск?

Данных мало.

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

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

Ну и, ещё, анализ оптимальности алгоритма сам по себе отнимает много времени.
Если это действительно нужно, надо полностью определить параметры задачи:
1) размер начального массива,
2) количество поисков,
3) что критичней: огромная задержка в 5% случаев или отсутствие вероятности такой задержки, но более долгая работа алгоритма в обычных случаях,
и т.п.



Это сообщение отредактировал(а) nworm - 18.1.2009, 01:08

За линейное время можно.

Сначала линейным проходом для каждого элемента A[i] находим ближайший к нему справа элемент, равный ему (это можно за O(N) одним проходом справа налево сделать). Пусть это массив Next[i] = позиция ближайшего справа элемента, совпадающего с A[i].

Затем идём слева направо, пусть текущая позиция в массиве A это i. Для каждого элемента поддерживаем позицию последней встречи этого элемента (до позиции i включительно), пусть это Last[j] (фактически, позиция ближайшего слева от [i] элемента, совпадающего с j). Чтобы поддерживать этот массив, понятно, нужно по O(1) операции на каждый шаг с i до i+1, собственно, аналогично массиву Next.

Тогда, чтобы найти элемент j, ближайший к позиции i, нужно будет посмотреть на Last[j] и Next[Last[j]]. Здесь мы использовали то, что позиции i по условию не уменьшаются, т.е. мы можем брать текущее значение массива Last[], использовать его, потом пересчитывать его до следующей позиции, обрабатывать следующий запрос, и т.д.

Итого O(N) на всё.

maxdiver, 
Спасибо, всё понятно . Проблема в том, что при следующем поиске некоторое количество элементов j может быть пропущено. 

Ну на сколько надо, на столько и шагаем. Всё равно мы всегда только вправо движемся, поэтому суммарно будет N шагов.

От нечего делать кодес накидал:

Я ещё подумал, что даже если запросы не строго возрастают, но задача в оффлайне (т.е. можно отвечать только после получения сразу всех запросов), то всё равно за линейное время решается - если запросы предварительно отсортировать подсчётом, и потом ту же шнягу повторить.

maxdiver, 
Огромное спасибо за код 



Задача в онлайне :(, некоторые позиции определяются на основании результатов предшествующих запросов.
Я уже сам задумался как решить для случайных позиций поиска. Но быстрее бинарного поиска ничего не придумал.

Добавлено через 4 минуты и 35 секунд
Изначально всё решалось матрицей размерности [n][s], s - размер алфавита. В матрице для каждой позиции определялась следующая позиция элемента i.

aggressorus
Если случайные позиции и в онлайне, то, мне кажется, быстрее бинарного поиска не получится.
Разве что вариант, о котором ты говорил, с таблицей N*S, но всё-таки O(N*S) скорее всего хуже, чем O(N*logN).