[wvxvw]

А почему был выбран именно массив? В упорядоченой, или частично упорядоченой коллекции поиск занимал бы заметно меньше времени.

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