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

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));
    }
}

ასევე, თუ დაშვებულია მასივის შეცვლა და საჭიროა მრავალჯერადი ძიება, შეგიძლიათ მასივი ერთხელ sort-ოთ (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]; // ძებნილი ელემენტი

        // ერთხელ sort-ოთ - 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 შეიძლება იყოს უფრო სწრაფი (წინასწარი სორტირების გარეშე), მაგრამ მოითხოვს დამატებით მეხსიერებას. მრავალჯერადი ძიებისთვის, სორტირებისა და ბინარული ძიების გამოყენება უფრო ეფექტურია დროის თვალსაზრისით თითოეული ძიებისთვის.

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