Exponential search algorithm in C#

Exponential Search is another searching algorithm that is primarily used for unbounded/infinite-sized arrays or arrays where the size is unknown. It works by exponentially increasing the range of search until the target element is found or the range exceeds the size of the array. Once the appropriate range is determined, a binary search is performed within that range to locate the target element.

Here's an illustration of the Exponential Search algorithm step by step, along with an example C# source code implementation:

using System;

class ExponentialSearchExample
{
    static int ExponentialSearch(int[] array, int target)
    {
        int n = array.Length;

        // If the target is the first element
        if (array[0] == target)
            return 0;

        // Find the range for binary search
        int i = 1;
        while (i < n && array[i] <= target)
            i *= 2;

        // Perform binary search within the determined range
        return BinarySearch(array, target, i / 2, Math.Min(i, n - 1));
    }

    static int BinarySearch(int[] array, int target, int low, int high)
    {
        while (low <= high)
        {
            int mid = low + (high - low) / 2;
            if (array[mid] == target)
                return mid;
            else if (array[mid] < target)
                low = mid + 1;
            else
                high = mid - 1;
        }

        return -1; // Target element not found
    }

    static void Main()
    {
        int[] array = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
        int target = 12;

        int index = ExponentialSearch(array, target);

        if (index == -1)
            Console.WriteLine("Element not found in the array.");
        else
            Console.WriteLine("Element found at index " + index);
    }
}

Explanation of the Exponential Search implementation:

1. The 'ExponentialSearch' function takes in an array and a target value as parameters and returns the index of the target value in the array (or -1 if not found).
2. If the target value is the first element of the array, it is checked separately and returns 0.
3. The algorithm starts by initializing the index 'i' to 1.
4. The algorithm repeatedly doubles the index 'i' until 'i' becomes larger than the array size or the element at 'i' is greater than the target value.
5. Once the appropriate range for the binary search is determined (from 'i/2' to 'Math.Min(i, n-1)'), the 'BinarySearch' function is called to perform the binary search within that range.
6. The 'BinarySearch' function is a standard binary search implementation. It takes the array, target value, lower bound, and upper bound as parameters and returns the index of the target value (or -1 if not found).
7. In the 'Main' method, we create an example array and set a target value of 12. We call the 'ExponentialSearch' function and display the result accordingly.

Note: The array must be sorted in ascending order for the Exponential Search algorithm to work correctly.