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

Αποκωδικοποίηση. Μπορείτε να δημιουργήσετε 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 (ns): " + (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("Χρόνος γραμμικής αναζήτησης (ns): " + (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("Χρόνος ταξινόμησης (ns): " + (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("Χρόνος δυαδικής αναζήτησης (ns): " + (endTime - startTime));
    }
}

Η επιλογή μεταξύ αποθήκευσης με κατακερματισμό και ταξινόμησης εξαρτάται από το πόσο συχνά θα γίνεται η αναζήτηση και αν επιτρέπεται η τροποποίηση του αρχικού πίνακα. Για μία ή σπάνια αναζήτηση, η αποθήκευση με κατακερματισμό μπορεί να είναι ταχύτερη (λόγω έλλειψης προκαταρκτικής ταξινόμησης), αλλά απαιτεί επιπλέον μνήμη. Για πολλαπλές αναζητήσεις μετά από μία μόνο προετοιμασία (ταξινόμηση), η δυαδική αναζήτηση είναι πιο αποδοτική σε χρόνο ανά αναζήτηση.

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