Задача:
Есть массив элементов, нужно максимально быстро определить есть ли в нем повторяющиеся элементы.
Решение которое напрашивается сразу:
Брать каждый элемент и сравнивать его с впереди стоящими, до тех пор пока не найдем равные или не дойдем до последнего. Итого придется сделать до n*(n-1)/2 сравнений.
Внимание, уважаемые знатоки, вопрос:
Это самый эффективный алгоритм? или есть лучше (если вообще существуют)?

Например, решение, которое напрашивается не стразу :
Прозводим сортировку массива, а далее сравниваем лишь соседние элементы. Итого, если будем использовать QSort, мы можем получить O(n*log n)*(n-1), т.е. O(n^2 * log n), а в худшем случае так вообще O(n^3). Вроде бы не лучше, но ведь можно модернизировать сортировку под наши цели, а также оптимизировать ее с учетом того, что известна некоторая статистическая информация о входных данных.

Более конкретная постановка задачи: проверяем корректность одного FAT сектора OLE2 контейнера ( WindowsCompoundBinaryFileFormatSpecification.pdf ). Такой сектор зачастую состоит из 128 DWORD'ов. Они зачастую располагаются возрастающими цепочками: 1h, 2h, 3h, ...., 12h. Между цепочками могут быть значения DWORD(-1), DWORD(-2), DWORD(-3) или DWORD(-4), которые вполне легально могут повторяться, остальные значения повторяться не могут.
Итак, повторю, надо максимально быстро проверить, что нет повторяющихся значений, кроме "легальных". Важен сам факт повтора, позиция и значение узнавать не обязательно. Вот такая вот задачка, прошу помощи =)

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

А после того как посмотрел сюда: http://ru.wikipedia.org/wiki/Пирамидальная_сортировка, то окончательно убедился, что вариант с деревьями возможно будет наилучшим.

Всем отписавшимся спасибо! =)