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

Hashing. Puedes crear un HashSet o HashMap a partir de los elementos de un 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); // Rellenar con números aleatorios
        }

        // Organización de búsqueda rápida con HashSet
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Buscar un elemento del array

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // O(1) en promedio
        long endTime = System.nanoTime();
        System.out.println("Encontrado: " + found);
        System.out.println("Tiempo de búsqueda en HashSet (ns): " + (endTime - startTime));

        // Búsqueda lineal para comparación - 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 (lineal): " + foundLinear);
        System.out.println("Tiempo de búsqueda lineal (ns): " + (endTime - startTime));
    }
}

Además, si se permite modificar el array y se requiere búsqueda múltiple, se puede ordenar el array una vez (Arrays.sort()) y luego usar búsqueda binaria (Arrays.binarySearch()). La ordenación tomará $O(n \log n)$, y cada búsqueda posterior - $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); // Rellenar con números aleatorios
        }

        int target = array[size / 2]; // Elemento a buscar

        // Ordenar una vez - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Tiempo de ordenación (ns): " + (endTime - startTime));

        // Búsqueda binaria - 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("Tiempo de búsqueda binaria (ns): " + (endTime - startTime));
    }
}

La elección entre hashing y ordenación depende de la frecuencia de búsqueda y si es aceptable modificar el array original. Para búsquedas únicas o poco frecuentes, el hashing puede ser más rápido (por la ausencia de ordenación previa), pero requiere memoria adicional. Para búsquedas múltiples, después de una preparación inicial (ordenación), la búsqueda binaria es más eficiente en tiempo por cada búsqueda.

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