C++/Sorting & Searching Programs/Program

Interpolation Search

Interpolation Search Algorithm in C++ (Complete Implementation)

C++Intermediate
C++
Try
#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

This program teaches you how to implement the Interpolation Search algorithm in C++. Interpolation Search is an improved variant of Binary Search that uses the value of the key to estimate its position in a sorted array. It's extremely fast for uniformly distributed data, achieving O(log log n) average time complexity.

1. What This Program Does

The program searches for an element in a sorted array using Interpolation Search. For example:

  • Sorted array: [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47]
  • Search for: 18
  • Result: Element found at index 4

Interpolation Search estimates the position of the key based on its value relative to the array's range, making it faster than Binary Search for uniformly distributed data.

2. Header File Used

#include <iostream>

This header provides:

  • cout for displaying output
  • cin for taking input from the user

3. Understanding Interpolation Search

Algorithm Concept:

  • Estimates key position using interpolation formula
  • Uses key value to calculate likely position
  • Similar to Binary Search but with smarter position calculation
  • Extremely fast for uniformly distributed data

Visual Example:

Array: [10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47] Search for: 18

Step 1: left=0, right=14, arr[0]=10, arr[14]=47

  • Position estimate: pos = 0 + ((14-0)/(47-10)) * (18-10) ≈ 3
  • Check arr[3] = 16 < 18 → search right

Step 2: left=4, right=14

  • Position estimate: pos = 4 + ((14-4)/(47-16)) * (18-16) ≈ 4
  • Check arr[4] = 18 == 18 → found!

4. Function: interpolationSearch()

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;
    }
    
    int pos = left + ((double)(right - left) / (arr[right] - arr[left])) * (key - arr[left]);
    
    if (arr[pos] == key) {
        return pos;
    }
    
    if (arr[pos] < key) {
        left = pos + 1;
    } else {
        right = pos - 1;
    }
}

return -1;

}

How it works:

  • Maintains search interval [left, right]
  • Calculates position using interpolation formula
  • Adjusts interval based on comparison
  • Continues until found or interval invalid

5. Understanding Interpolation Formula

Formula:

pos = left + ((right - left) / (arr[right] - arr[left])) * (key - arr[left])

How it works:

  • (key - arr[left]) / (arr[right] - arr[left]): proportion of key in range
  • (right - left): size of current interval
  • Multiplies proportion by interval size
  • Adds to left to get estimated position

Example (searching for 18):

  • left=0, right=14, arr[0]=10, arr[14]=47, key=18
  • Proportion: (18-10)/(47-10) = 8/37 ≈ 0.216
  • Position: 0 + 0.216 * 14 ≈ 3
  • arr[3] = 16 < 18 → adjust and recalculate

6. Step-by-Step Algorithm

Step 1: Initialize Interval

  • left = 0, right = n - 1
  • Check bounds: key >= arr[left] && key <= arr[right]

Step 2: Calculate Position

  • Use interpolation formula to estimate position
  • Formula considers key value relative to array range

Step 3: Compare

  • If arr[pos] == key: found, return pos
  • If arr[pos] < key: search right half, left = pos + 1
  • If arr[pos] > key: search left half, right = pos - 1

Step 4: Repeat

  • Continue while left <= right and key in range
  • If interval invalid: key not found, return -1

7. Time and Space Complexity

Time Complexity:

  • Best case: O(1) - key at estimated position
  • Average case: O(log log n) - uniformly distributed data
  • Worst case: O(n) - non-uniform distribution

Space Complexity: O(1)

  • Only uses constant extra space
  • Variables: left, right, pos
  • No additional arrays or recursion

8. When to Use Interpolation Search

Best For:

  • Sorted arrays with uniform distribution
  • When data is evenly spaced
  • When average performance is critical
  • Large uniformly distributed datasets

Not Recommended For:

  • Non-uniformly distributed data (degrades to O(n))
  • When worst-case O(n) is unacceptable
  • Small arrays (overhead not worth it)
  • When data distribution is unknown

9. Comparison with Binary Search

Interpolation Search Advantages:

  • Faster average case: O(log log n) vs O(log n)
  • Uses key value for smarter position estimation
  • Better for uniformly distributed data

Interpolation Search Disadvantages:

  • Worst case: O(n) vs O(log n) for Binary Search
  • Requires uniform distribution for best performance
  • More complex position calculation

Binary Search Advantages:

  • Guaranteed O(log n) in all cases
  • Works well regardless of distribution
  • Simpler implementation

10. Important Considerations

Uniform Distribution Requirement:

  • Best performance when data is uniformly distributed
  • Non-uniform data can degrade to O(n)
  • Example: [1, 2, 3, 1000, 1001, 1002] - poor for interpolation

Bounds Checking:

  • key >= arr[left] && key <= arr[right]
  • Prevents division by zero
  • Ensures key is in valid range

Position Calculation:

  • Uses double for division to maintain precision
  • Important for accurate position estimation
  • Cast to int for array index

11. return 0;

This ends the program successfully.

Summary

  • Interpolation Search estimates key position using interpolation formula based on key value.
  • Time complexity: O(log log n) average, O(n) worst case.
  • Space complexity: O(1) - only uses constant extra space.
  • Requires sorted array and works best with uniform distribution.
  • Faster than Binary Search for uniformly distributed data.
  • Position formula: pos = left + proportion * (right - left).
  • Understanding Interpolation Search demonstrates advanced searching techniques.
  • Best choice when data is uniformly distributed and average performance matters.

This program is fundamental for learning advanced search algorithms, understanding interpolation techniques, and preparing for performance-optimized searching in C++ programs.

Previous
Jump Search