Как можно организовать быстрый поиск в…

Хеширане. Можете да създадете 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));
    }
}

Изборът между хеширане и сортиране зависи от това колко често ще се извършва търсенето и дали е допустимо изменение на оригиналния масив. За еднократно или рядко търсене хеширането може да е по-бързо (заради липсата на предварително сортиране), но изисква допълнителна памет. За многократно търсене след еднократно подготвяне (сортиране) двоичното търсене е по-ефективно по време на всяко търсене.

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