package com.thealgorithms.searches;

import com.thealgorithms.devutils.searches.SearchAlgorithm;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

/**
 * A Random Search algorithm that randomly selects an index and checks if the
 * value at that index matches the target. It repeats the process until it
 * finds the target or checks all elements.
 *
 * <p>
 * Time Complexity: O(n) in the worst case.
 * </p>
 *
 * @author Hardvan
 */
public class RandomSearch implements SearchAlgorithm {

    private final Random random = new Random();

    /**
     * Finds the index of a given element using random search.
     *
     * @param array Array to search through
     * @param key Element to search for
     * @return Index of the element if found, -1 otherwise
     */
    @Override
    public <T extends Comparable<T>> int find(T[] array, T key) {
        Set<Integer> visitedIndices = new HashSet<>();
        int size = array.length;

        while (visitedIndices.size() < size) {
            int randomIndex = random.nextInt(size);
            if (array[randomIndex].compareTo(key) == 0) {
                return randomIndex;
            }
            visitedIndices.add(randomIndex);
        }

        return -1;
    }
}