Существование элемента в массиве

[Carbon]

Есть последовательность чисел (например, берётся из файла), максимум длины 70000. Числа пронумерованы 1..n. Далее вводятся 3 числа l, r, v. Определить, существует ли v в последовательности от номера l до r (вывести 1) или нет (вывести 0). Нужно осуществить поиск как можно быстрее.

[Hollander]

Быстрее чем обычный перебор у тебя ничего не получиться, за исключением случаю, что у тебя массив отсортирован. А так:
ar - это массив куда ты заггрузишь всю последовательность

flag := false;
for i:= l to r do
if v=ar[i] then 
begin
flag:= true;
break;
end;
if flag = true then
writeln('1')
else writeln('0');

[Carbon]

У меня получалось быстрее:
1) пирамидальная сортировка+бинарный поиск.
2) создание бинарного дерева+поиск по дереву
3) разбивал на сегменты с шагом 100 и списком записывал элементы (хорошо только при равномерном разбросе)
Только всё по тайм лимиту не влазило.

[alexBlack]

У меня получалось быстрее ...

Carbon, что-то не сходится. Чтобы отсортировать последовательность нужно как минимум пройти по всем ее элементам. За это время можно найти элемент, удовлетворяющий условиям.

Или метод решения задан и надо обязательно сортировать, а потом искать ?

[Carbon]

Вся загвоздка в том, что запросов "Определить, существует ли v в последовательности от номера l до r (вывести 1) или нет (вывести 0)." может быть ОЧЕНЬ много.

[alexBlack]

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

А если такой вариант: при чтении формируем элементы:

<Число <список позиций, в который встречается> >

Элементы сортируем по "Число". Списки позиций сами получится сортированные.

Тогда чисел уже будет меньше 70000 - должны же там быть повторы.
Кстати, на числа есть какие-то ограничения ? В списке диапазонов ищем позицию.

[Carbon]

0 - 10^9-1

[alexBlack]

Этот вариант отпадает. Подумаю.

[Carbon]

Можно как вариант:

Сообщение от Carbon

2) создание бинарного дерева+поиск по дереву

Но он не прошёл, т.к. числа, похоже, были отсортированы. А можно уравновесить дерево, чтобы для каждого узла слева и справа было примерно одинаковое количество элементов?

[alexBlack]

Ага, это называется сбалансированное дерево.

Вот реализация. Только без удаления узлов. Но, в этом случае удаления не понадобится. Код делал на основе примера из Вирт "Алгоритмы..."