How can you organize a quick search in an unsorted array of integers containing millions of values?

Hashing. You can create a HashSet or HashMap from array elements.

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); // Fill with random numbers
        }

        // Organize quick search using HashSet
        HashSet<Integer> set = new HashSet<>(size);
        for (int value : array) {
            set.add(value);
        }

        int target = array[size / 2]; // Search for an element from the array

        long startTime = System.nanoTime();
        boolean found = set.contains(target); // O(1) on average
        long endTime = System.nanoTime();
        System.out.println("Found: " + found);
        System.out.println("Search time in HashSet (ns): " + (endTime - startTime));

        // Linear search for comparison - O(n)
        startTime = System.nanoTime();
        boolean foundLinear = false;
        for (int value : array) {
            if (value == target) {
                foundLinear = true;
                break;
            }
        }
        endTime = System.nanoTime();
        System.out.println("Found (linear): " + foundLinear);
        System.out.println("Linear search time (ns): " + (endTime - startTime));
    }
}

Also, if array modification is allowed and multiple searches are needed, you can sort the array once (Arrays.sort()) and then use binary search (Arrays.binarySearch()). Sorting takes $O(n \log n)$, and each subsequent search takes $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); // Fill with random numbers
        }

        int target = array[size / 2]; // Element to search for

        // Sort once - O(n log n)
        long startTime = System.nanoTime();
        Arrays.sort(array);
        long endTime = System.nanoTime();
        System.out.println("Sorting time (ns): " + (endTime - startTime));

        // Binary search - O(log n)
        startTime = System.nanoTime();
        int index = Arrays.binarySearch(array, target);
        endTime = System.nanoTime();
        boolean found = index >= 0;
        System.out.println("Found: " + found);
        System.out.println("Binary search time (ns): " + (endTime - startTime));
    }
}

The choice between hashing and sorting depends on how often searches will occur and whether modifying the original array is acceptable. For one-time or infrequent searches, hashing may be faster (due to no initial sorting), but requires additional memory. For multiple searches after a one-time setup (sorting), binary search is more time-efficient per search.