Interpolation search

Interpolation search is a searching algorithm that improves upon the efficiency of binary search when the elements in the collection are uniformly distributed. It calculates the probable position of the target value based on its value and the values of the first and last elements in the collection. Interpolation search narrows down the search space by estimating the position of the target element within the collection.

Here's an illustration of interpolation search using a step-by-step C# example:

using System;

class Program
{
    static void Main()
    {
        int[] arr = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
        int target = 23;

        int index = InterpolationSearch(arr, target);

        if (index != -1)
        {
            Console.WriteLine($"Element {target} found at index {index}");
        }
        else
        {
            Console.WriteLine("Element not found");
        }
    }

    static int InterpolationSearch(int[] arr, int target)
    {
        int left = 0;
        int right = arr.Length - 1;

        while (left <= right && target >= arr[left] && target <= arr[right])
        {
            // Estimate the position using interpolation formula
            int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);

            if (arr[pos] == target)
            {
                return pos; // Return the index if the element is found
            }
            else if (arr[pos] < target)
            {
                left = pos + 1; // Search in the right half
            }
            else
            {
                right = pos - 1; // Search in the left half
            }
        }

        return -1; // Return -1 if the element is not found
    }
}

Let's break down the steps of interpolation search using this example:

1. We have a sorted array arr containing elements in ascending order ('arr = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 }') and a target value that we want to find ('target = 23').
2. We initialize two pointers, left and right, which represent the leftmost and rightmost indices of the current search range. In this case, 'left = 0' and 'right = arr.Length - 1 = 9'.
3. The algorithm calculates the probable position of the target element using the interpolation formula: 'pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]')
4. The formula estimates the position based on the values of the target, the first element, and the last element in the current search range.
5. The algorithm compares the value at the estimated position ('arr[pos]') with the target value.
   • If they are equal, the target element is found, and the algorithm returns the index pos.
   • If 'arr[pos]' is less than the target, the algorithm narrows down the search range to the right half by updating 'left = pos + 1'.
   • If 'arr[pos]' is greater than the target, the algorithm narrows down the search range to the left half by updating 'right = pos - 1'.
6. The algorithm repeats steps 3 and 4 until either the target element is found or the search range is exhausted ('left > right'). If the search range is exhausted, it means the target element is not present in the array, and the algorithm returns -1.

In this example, the interpolation search algorithm determines that the target value 23 is located at index 5 in the array ('arr[5]'). The program outputs: "Element 23 found at index 5".

Interpolation search performs well when the elements in the collection are uniformly distributed. However, it may exhibit poor performance or even fail to converge efficiently in cases where the distribution is uneven or the array contains repeated elements.

Note: It is important to ensure that the array is sorted before using interpolation search. If the array is unsorted, it is necessary to sort it first or use another sorting algorithm.