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

Hashing. Létrehozhatsz HashSet vagy HashMap-et egy tömb elemeiből.

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); // Véletlenszerű számokkal töltjük fel
        }

        // Gyors keresés szervezése HashSet segítségével
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Egy elem keresése a tömbből

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // Átlagosan O(1)
        long endTime = System.nanoTime();
        System.out.println("Találva: " + found);
        System.out.println("Keresési idő HashSet-ben (ns): " + (endTime - startTime));

        // Lineáris keresés összehasonlításként - O(n)
        startTime = System.nanoTime();
        boolean foundLinear = false;
        for (int value : array) {
            if (value == target) {
                foundLinear = true;
                break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Találva (lineáris): " + foundLinear);
        System.out.println("Lineáris keresési idő (ns): " + (endTime - startTime));
    }
}

Továbbá, ha megengedett a tömb módosítása és többszöri keresésre van szükség, egyszerűen rendezheted a tömböt (Arrays.sort()) és utána használhatod a bináris keresést (Arrays.binarySearch()). A rendezés $O(n \log n)$-t vesz igénybe, minden további keresés pedig $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); // Véletlenszerű számokkal töltjük fel
        }

        int target = array[size / 2]; // Keresett elem

        // Egyszeri rendezés - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Rendezési idő (ns): " + (endTime - startTime));

        // Bináris keresés - O(log n)
        startTime = System.nanoTime();
        int index = Arrays.binarySearch(array, target);
        endTime = System.nanoTime();
        boolean found = index >= 0;
        System.out.println("Találva: " + found);
        System.out.println("Bináris keresés idő (ns): " + (endTime - startTime));
    }
}

A választás a hash-elés és a rendezés között attól függ, hogy milyen gyakran fog történni a keresés és hogy megengedhető-e a tömb módosítása. Egyszeri vagy ritka keresés esetén a hash-elés gyorsabb lehet (a rendezés hiánya miatt), de extra memóriát igényel. Többszöri keresés esetén a rendezés utáni bináris keresés hatékonyabb minden keresésnél.

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