Program Explanation

The interpolation search algorithm is an improved variant of binary search that works on sorted, uniformly distributed arrays. Unlike binary search, which divides the search space in half, interpolation search uses the value of the target to estimate the position in the array, which can lead to faster search times for uniformly distributed data.

Program Structure

#include <iostream>
using namespace std;

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

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

        // Check if the target value is found
        if (arr[pos] == x) {
            return pos; // Return the position of the target value
        }
        
        // If the target value is greater, move the low pointer
        if (arr[pos] < x) {
            low = pos + 1;
        } 
        // If the target value is smaller, move the high pointer
        else {
            high = pos - 1;
        }
    }
    
    return -1; // Target value not found
}

// Main function to test the interpolation search
int main() {
    int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 70; // Target value to search

    int result = interpolationSearch(arr, n, x);
    
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found." << endl;
    }

    return 0;
}

Documentation

• Function: interpolationSearch
  • Parameters:
    • int arr[]: The sorted array of integers.
    • int n: The number of elements in the array.
    • int x: The target value to search for.
  • Returns: The index of the target value if found, otherwise -1.
• Main Function
  • Defines a sample sorted array and the target value.
  • Calls the interpolationSearch function and displays the result.

Conclusion

Interpolation search is efficient for large datasets with uniformly distributed values, providing better average performance compared to binary search. However, it can degrade to linear search in the worst-case scenario. Understanding when to use interpolation search can significantly enhance search operations in appropriate data sets.