Как можно организовать быстрый поиск в неотсортированном массиве целых чисел, содержащем миллионы значений?

Хеширование. Можно создать HashSet или HashMap из элементов массива.

java

Также, если допустимо изменение массива и требуется многократный поиск, можно отсортировать массив один раз (Arrays.sort()