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

Hashleme. Bir HashSet veya HashMap oluşturmak için dizi öğelerini kullanabilirsiniz.

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); // Rastgele sayılarla doldur
        }

        // Hızlı arama için HashSet kullanımı
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Dizi içinden bir öğe ara

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // Ortalama O(1)
        long endTime = System.nanoTime();
        System.out.println("Bulundu: " + found);
        System.out.println("HashSet'te arama süresi (ns): " + (endTime - startTime));

        // Karşılaştırmak için doğrusal arama - O(n)
        startTime = System.nanoTime();
        boolean foundLinear = false;
        for (int value : array) {
            if (value == target) {
                foundLinear = true;
                break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Bulundu (doğrusal): " + foundLinear);
        System.out.println("Doğrusal arama süresi (ns): " + (endTime - startTime));
    }
}

Ayrıca, dizi üzerinde değişiklik yapılmasına izin veriliyorsa ve çoklu arama gerekiyorsa, diziyi bir kez sıralayabilir (Arrays.sort()) ve ardından ikili arama (Arrays.binarySearch()) kullanabilirsiniz. Sıralama $O(n \log n)$ zaman alır ve sonraki her arama - $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); // Rastgele sayılarla doldur
        }

        int target = array[size / 2]; // Aranacak öğe

        // Bir kez sıralama - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Sıralama süresi (ns): " + (endTime - startTime));

        // İkili arama - O(log n)
        startTime = System.nanoTime();
        int index = Arrays.binarySearch(array, target);
        endTime = System.nanoTime();
        boolean found = index >= 0;
        System.out.println("Bulundu: " + found);
        System.out.println("İkili arama süresi (ns): " + (endTime - startTime));
    }
}

Hashing ile sıralama arasındaki seçim, arama sıklığına ve orijinal diziyi değiştirmeye izin verilip verilmediğine bağlıdır. Tek seferlik veya nadiren yapılan aramalar için hashleme daha hızlı olabilir (önceden sıralama olmadan), ancak ek bellek gerektirir. Çoklu aramalar için, hazırlıktan sonra (sıralama) ikili arama zaman açısından daha etkilidir.

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