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

Hashimine. Võite luua HashSet või HashMap massiivi elementidest.

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); // Täidame juhuslike numbritega
        }

        // Kiire otsingu korraldamine HashSet abil
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Otsime massiivist elementi

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // Keskmiselt O(1)
        long endTime = System.nanoTime();
        System.out.println("Leitud: " + found);
        System.out.println("Otsingu aeg HashSetis (ns): " + (endTime - startTime));

        // Lineaarne otsing võrdluseks - O(n)
        startTime = System.nanoTime();
        boolean foundLinear = false;
        for (int value : array) {
            if (value == target) {
                foundLinear = true;
                break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Leitud (lineaarne): " + foundLinear);
        System.out.println("Lineaarse otsingu aeg (ns): " + (endTime - startTime));
    }
}

Samuti, kui on lubatud muuta massiivi ja on vaja korduvat otsingut, saab ühe korraga sorteerida massiivi (Arrays.sort()) ja kasutada binaarset otsingut (Arrays.binarySearch()). Sorteerimine võtab $O(n \log n)$, iga järgnev otsing - $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); // Täidame juhuslike numbritega
        }

        int target = array[size / 2]; // Otsitav element

        // Sorteerime ühe korra - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Sorteerimise aeg (ns): " + (endTime - startTime));

        // Binaarne otsing - O(log n)
        startTime = System.nanoTime();
        int index = Arrays.binarySearch(array, target);
        endTime = System.nanoTime();
        boolean found = index >= 0;
        System.out.println("Leitud: " + found);
        System.out.println("Binaarse otsingu aeg (ns): " + (endTime - startTime));
    }
}

Valik hashimise ja sortimise vahel sõltub sellest, kui sageli otsinguid tehakse ja kas algset massiivi tohib muuta. Ühekordse või harva tehtava otsingu puhul võib hashimine olla kiirem (ilma eelneva sortimiseta), kuid nõuab lisamälu. Mitmekordse otsingu puhul on pärast ühekorralist sorteerimist binarotsing aja kokkuhoid iga otsingu puhul.

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