Jump search algorithm in C#

Jump Search is an algorithm used to search for an element in a sorted array. It is similar to binary search, but instead of dividing the array into two equal halves, it jumps forward in fixed steps to reduce the number of comparisons.

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

using System;

class JumpSearchExample
{
    static int JumpSearch(int[] array, int target)
    {
        int n = array.Length;
        int step = (int)Math.Floor(Math.Sqrt(n));
        int prev = 0;

        while (array[Math.Min(step, n) - 1] < target)
        {
            prev = step;
            step += (int)Math.Floor(Math.Sqrt(n));
            if (prev >= n)
                return -1;
        }

        while (array[prev] < target)
        {
            prev++;
            if (prev == Math.Min(step, n))
                return -1;
        }

        if (array[prev] == target)
            return prev;

        return -1;
    }

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

        int index = JumpSearch(array, target);

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

1. The 'JumpSearch' 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. The length of the array is stored in the variable n, and the step size for jumping is set to the square root of 'n' using 'Math.Sqrt'.
3. The algorithm starts by comparing the target value with the element at index 'step - 1' in the array. If the target is greater, it jumps forward by increasing the step size and updates the 'prev' variable to the previous step's index.
4. Once the target value is not greater than the current element, the algorithm performs a linear search between the previous step and the current step to find the target value.
5. If the target value is found, the index is returned. Otherwise, if the loop ends without finding the target, -1 is returned.
6. In the 'Main' method, we create an example array and set a target value of 12. We call the 'JumpSearch' function and display the result accordingly.

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