Исправление aedeph_, 13.05.15 15:34 (текущая версия) :
Считай хеш, сортируй, ищи бинарным поиском.
\Theta(n) + \Theta(n log n) + \Theta(log n)
Исходная версия aedeph_, 13.05.15 15:33:
\Theta(N) + \Theta(n log n) + \Theta(log n)