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

Hashing. Կարող եք ստեղծել 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));
    }
}

Ընտրությունը hashing կամ sorting-ը կախված է այն բանից, թե որքան հաճախ է կատարվելու որոնումը և արդյոք թույլատրվում է փոփոխել սկզբնական զանգվածը: Միակ կամ հազվագյուտ որոնումների դեպքում hashing-ը կարող է լինել ավելի արագ (առանց նախնական դասավորության), բայց պահանջում է լրացուցիչ հիշողություն: Մեծ քանակությամբ որոնումների դեպքում, նախապես դասավորած զանգվածի համար, բինար որոնումը ավելի արդյունավետ է ժամանակի տեսանկյունից յուրաքանչյուր որոնման համար։

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