The Interpolation Search is an improved variant of binary search. It works on the principle of estimating the position of the target value based on the value’s range in a sorted array. This method is more efficient for uniformly distributed data.

Program Structure

#include 

// Function to perform interpolation search
int interpolationSearch(int arr[], int size, int target) {
    int low = 0, high = size - 1;

    while (low <= high && target >= arr[low] && target <= arr[high]) {
        // Estimate the position of the target value
        int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);

        // Check if the target value is at the estimated position
        if (arr[pos] == target) {
            return pos;  // Target found
        }

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

// Main function
int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int size = sizeof(arr) / sizeof(arr[0]);
    int target = 70;

    int result = interpolationSearch(arr, size, target);
    if (result != -1) {
        printf("Element found at index: %d\n", result);
    } else {
        printf("Element not found.\n");
    }

    return 0;
}

Documentation