Interpolation Search

Interpolation Search Algorithm in C++ (Complete Implementation)

IntermediateTopic: Sorting & Searching Programs
Back

C++ Interpolation Search Program

This program helps you to learn the fundamental structure and syntax of C++ programming.

Try This Code
#include <iostream>
using namespace std;

int interpolationSearch(int arr[], int n, int key) {
    int left = 0;
    int right = n - 1;
    
    while (left <= right && key >= arr[left] && key <= arr[right]) {
        if (left == right) {
            if (arr[left] == key) {
                return left;
            }
            return -1;
        }
        
        // Calculate position using interpolation formula
        int pos = left + ((double)(right - left) / (arr[right] - arr[left])) * (key - arr[left]);
        
        if (arr[pos] == key) {
            return pos;  // Found
        }
        
        if (arr[pos] < key) {
            left = pos + 1;  // Search right
        } else {
            right = pos - 1;  // Search left
        }
    }
    
    return -1;  // Not found
}

int main() {
    int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
    int n = sizeof(arr) / sizeof(arr[0]);
    int key;
    
    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    
    cout << "Enter element to search: ";
    cin >> key;
    
    int result = interpolationSearch(arr, n, key);
    
    if (result != -1) {
        cout << "Element found at index: " << result << endl;
    } else {
        cout << "Element not found in array" << endl;
    }
    
    return 0;
}
Output
Sorted array: 10 12 13 16 18 19 20 21 22 23 24 33 35 42 47
Enter element to search: 18
Element found at index: 4

Understanding Interpolation Search

Interpolation Search is an improved variant of binary search for uniformly distributed sorted arrays. It uses the value of the key to estimate its position. Time Complexity: O(log log n) average, O(n) worst case. Space Complexity: O(1). It's faster than binary search when elements are uniformly distributed.

Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.

Previous
Jump Search

Table of Contents