package com.thealgorithms.searches;

import com.thealgorithms.devutils.searches.SearchAlgorithm;
import java.util.Arrays;

/**
 * ExponentialSearch is an algorithm that efficiently finds the position of a target
 * value within a sorted array. It works by expanding the range to find the bounds
 * where the target might exist and then using binary search within that range.
 *
 * <p>
 * Worst-case time complexity: O(log n)
 * Best-case time complexity: O(1) when the element is found at the first position.
 * Average time complexity: O(log n)
 * Worst-case space complexity: O(1)
 * </p>
 *
 * <p>
 * Note: This algorithm requires that the input array be sorted.
 * </p>
 */
class ExponentialSearch implements SearchAlgorithm {

    /**
     * Finds the index of the specified key in a sorted array using exponential search.
     *
     * @param array The sorted array to search.
     * @param key The element to search for.
     * @param <T> The type of the elements in the array, which must be comparable.
     * @return The index of the key if found, otherwise -1.
     */
    @Override
    public <T extends Comparable<T>> int find(T[] array, T key) {
        if (array.length == 0) {
            return -1;
        }
        if (array[0].equals(key)) {
            return 0;
        }
        if (array[array.length - 1].equals(key)) {
            return array.length - 1;
        }

        int range = 1;
        while (range < array.length && array[range].compareTo(key) < 0) {
            range = range * 2;
        }

        return Arrays.binarySearch(array, range / 2, Math.min(range, array.length), key);
    }
}