Overview

The Exponential Search algorithm is an efficient search algorithm designed for unbounded or infinite lists. It works by first finding a range where the target element might reside and then performing a binary search within that range. This combination allows it to operate faster than traditional search methods in certain scenarios.

Program Structure

The Java implementation consists of the following key components:

• exponentialSearch: This method performs the exponential search algorithm.
• binarySearch: A helper method that performs binary search on a specified range.
• main: The entry point of the program, where we define the array and the target value.

Java Code

public class ExponentialSearch {

    // Exponential Search algorithm
    public static int exponentialSearch(int[] arr, int target) {
        // If the target is at the first position
        if (arr[0] == target) {
            return 0;
        }

        // Find range for binary search
        int i = 1;
        while (i < arr.length && arr[i] <= target) {
            i *= 2;
        }

        // Call binary search for the found range
        return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), target);
    }

    // Binary Search algorithm
    private static int binarySearch(int[] arr, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // Check if target is present at mid
            if (arr[mid] == target) {
                return mid;
            }

            // If target is greater, ignore left half
            if (arr[mid] < target) {
                left = mid + 1;
            }
            // If target is smaller, ignore right half
            else {
                right = mid - 1;
            }
        }
        // Target not found
        return -1;
    }

    // Main method
    public static void main(String[] args) {
        int[] arr = {2, 3, 4, 10, 40};
        int target = 10;

        int result = exponentialSearch(arr, target);
        if (result == -1) {
            System.out.println("Element not found in the array.");
        } else {
            System.out.println("Element found at index: " + result);
        }
    }
}

Explanation of the Code

The code begins with the exponentialSearch method, which first checks if the target element is at the beginning of the array. If not, it progressively doubles the index i until it finds a range where the target might be located. Once the appropriate range is determined, it calls the binarySearch method.

The binarySearch method performs a standard binary search. It divides the search space in half, checking the middle element and adjusting the search bounds accordingly until it finds the target or determines that the target is not present.

Complexity Analysis

The time complexity of Exponential Search is O(log i), where i is the index of the target element. The space complexity is O(1) as it uses a constant amount of space.

Conclusion

Exponential Search is a powerful search algorithm for unbounded lists, combining the efficiency of exponential searching with binary search. This Java implementation showcases its effectiveness and serves as a basis for understanding advanced searching techniques.