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

Hashing. Pode criar um HashSet ou um HashMap a partir dos elementos de um array.

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); // Preencher com números aleatórios
        }

        // Organização de busca rápida com HashSet
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Procurar um elemento do array

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // O(1) em média
        long endTime = System.nanoTime();
        System.out.println("Encontrado: " + found);
        System.out.println("Tempo de busca no HashSet (ns): " + (endTime - startTime));

        // Busca linear para comparação - O(n)
        startTime = System.nanoTime();
        boolean foundLinear = false;
        for (int value : array) {
            if (value == target) {
                foundLinear = true;
                break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Encontrado (linear): " + foundLinear);
        System.out.println("Tempo de busca linear (ns): " + (endTime - startTime));
    }
}

Além disso, se for permitido modificar o array e for necessária uma busca múltipla, pode ordenar o array uma vez (Arrays.sort()) e depois usar busca binária (Arrays.binarySearch()). A ordenação levará $O(n \log n)$, e cada busca subsequente - $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); // Preencher com números aleatórios
        }

        int target = array[size / 2]; // Elemento para busca

        // Ordenar uma vez - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Tempo de ordenação (ns): " + (endTime - startTime));

        // Busca binária - O(log n)
        startTime = System.nanoTime();
        int index = Arrays.binarySearch(array, target);
        endTime = System.nanoTime();
        boolean found = index >= 0;
        System.out.println("Encontrado: " + found);
        System.out.println("Tempo de busca binária (ns): " + (endTime - startTime));
    }
}

A escolha entre hashing e ordenação depende da frequência de busca e se é aceitável modificar o array original. Para buscas únicas ou pouco frequentes, o hashing pode ser mais rápido (devido à ausência de ordenação prévia), mas requer memória adicional. Para buscas múltiplas, após uma preparação inicial (ordenar), a busca binária é mais eficiente em tempo para cada busca.

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