What is Interpolation Search?

Interpolation search is a search algorithm used to find the position of a target value within a sorted array.
It improves upon the binary search algorithm by estimating the position of the target value based on the values
of the array elements. This technique works best on uniformly distributed data.

Program Structure

The implementation of the interpolation search algorithm consists of the following main components:

• Function Definition: A function named interpolation_search(arr, target) that takes a sorted array and a target value.
• Variable Initialization: Initializing left and right pointers to the start and end of the array.
• Looping through the Array: Using a loop to calculate the estimated position of the target value.
• Checking Conditions: Checking if the target value is present at the estimated position,
  or adjusting the left or right pointers based on the comparison.
• Return Result: Returning the index of the target value if found, otherwise returning -1.

Python Implementation

def interpolation_search(arr, target):
    """
    Perform interpolation search on a sorted array.

    :param arr: A list of sorted elements
    :param target: The value to search for
    :return: The index of the target value if found; otherwise, -1
    """
    left = 0
    right = len(arr) - 1

    while left <= right and target >= arr[left] and target <= arr[right]:
        # Estimate the position using the formula
        pos = left + ((right - left) // (arr[right] - arr[left]) * (target - arr[left]))

        # Check if the target is present at pos
        if arr[pos] == target:
            return pos

        # If target is larger, ignore left half
        if arr[pos] < target:
            left = pos + 1
        # If target is smaller, ignore right half
        else:
            right = pos - 1

    return -1  # Target not found

# Example usage
if __name__ == "__main__":
    arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
    target = 70
    result = interpolation_search(arr, target)

    if result != -1:
        print(f"Element found at index: {result}")
    else:
        print("Element not found in the array.")

How to Run the Program

To run the above program, you can copy the code into a Python (.py) file and execute it in your terminal or command prompt.
Make sure you have Python installed on your system. You can also use an online Python compiler for quick testing.

Conclusion

Interpolation search is an efficient algorithm for searching in sorted arrays, especially when the data is uniformly distributed.
The time complexity of the interpolation search is O(log log n) for uniformly distributed data, making it faster than binary search in many scenarios.