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

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

import java.util.HashSet;
import java.util.Random;

public class SearchExample {

    public static void main(String[] args) {
        int size = 1000000;
        int[] array = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size * 10); // Заполняем случайными числами
        }

        // Организация быстрого поиска с помощью HashSet
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Ищем элемент из массива

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // O(1) в среднем
        long endTime = System.nanoTime();
        System.out.println("Найдено: " + found);
        System.out.println("Время поиска в HashSet (нс): " + (endTime - startTime));

        // Линейный поиск для сравнения - O(n)
        startTime = System.nanoTime();
        boolean foundLinear = false;
        for (int value : array) {
            if (value == target) {
                foundLinear = true;
                break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Найдено (линейный): " + foundLinear);
        System.out.println("Время линейного поиска (нс): " + (endTime - startTime));
    }
}

Также, если допустимо изменение массива и требуется многократный поиск, можно отсортировать массив один раз (Arrays.sort()) и затем использовать бинарный поиск (Arrays.binarySearch()). Сортировка займет $O(n \log n)$, а каждый последующий поиск - $O(\log n)$.

import java.util.Arrays;
import java.util.Random;

public class SortedSearchExample {

     public static void main(String[] args) {
        int size = 1000000;
        int[] array = new int[size];
        Random random = new Random();
        for (int i = 0; i < size; i++) {
            array[i] = random.nextInt(size * 10); // Заполняем случайными числами
        }

        int target = array[size / 2]; // Элемент для поиска

        // Сортировка один раз - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Время сортировки (нс): " + (endTime - startTime));

        // Бинарный поиск - O(log n)
        startTime = System.nanoTime();
        int index = Arrays.binarySearch(array, target);
        endTime = System.nanoTime();
        boolean found = index >= 0;
        System.out.println("Найдено: " + found);
        System.out.println("Время бинарного поиска (нс): " + (endTime - startTime));
    }
}

Выбор между хешированием и сортировкой зависит от того, насколько часто будет происходить поиск и допустимо ли изменение исходного массива. Для однократного или редкого поиска хеширование может быть быстрее (из-за отсутствия предварительной сортировки), но требует дополнительной памяти. Для многократного поиска после однократной подготовки (сортировки) бинарный поиск эффективнее по времени на каждый поиск.