RandomSearch.java

packagecom.thealgorithms.searches;

importcom.thealgorithms.devutils.searches.SearchAlgorithm;
importjava.util.HashSet;
importjava.util.Random;
importjava.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
 */
publicclassRandomSearchimplementsSearchAlgorithm {

privatefinalRandomrandom = newRandom();

/**
 * 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 <TextendsComparable<T>> intfind(T[] array, Tkey) {
Set<Integer> visitedIndices = newHashSet<>();
intsize = array.length;

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

return -1;
 }
}