Interpolation Search in C++
Interpolation Search Algorithm in C++ (Complete Implementation).
IntermediateSorting & Searching ProgramsExample 13 of 13
interpolation-search.cpp
1#include <iostream>2using namespace std;34int interpolationSearch(int arr[], int n, int key) {5 int left = 0;6 int right = n - 1;78 while (left <= right && key >= arr[left] && key <= arr[right]) {9 if (left == right) {10 if (arr[left] == key) {11 return left;12 }13 return -1;14 }1516 // Calculate position using interpolation formula17 int pos = left + ((double)(right - left) / (arr[right] - arr[left])) * (key - arr[left]);1819 if (arr[pos] == key) {20 return pos; // Found21 }2223 if (arr[pos] < key) {24 left = pos + 1; // Search right25 } else {26 right = pos - 1; // Search left27 }28 }2930 return -1; // Not found31}3233int main() {34 int arr[] = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};35 int n = sizeof(arr) / sizeof(arr[0]);36 int key;3738 cout << "Sorted array: ";39 for (int i = 0; i < n; i++) {40 cout << arr[i] << " ";41 }42 cout << endl;4344 cout << "Enter element to search: ";45 cin >> key;4647 int result = interpolationSearch(arr, n, key);4849 if (result != -1) {50 cout << "Element found at index: " << result << endl;51 } else {52 cout << "Element not found in array" << endl;53 }5455 return 0;56}
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
What's going on
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.
Header File Used
This header provides:
cout for displaying output
cin for taking input from the user
1#include <iostream>
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!
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 -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;
}
1return left;
How it works
:
Maintains search interval [left, right]
Calculates position using interpolation formula
Adjusts interval based on comparison
Continues until found or interval invalid
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
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
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
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
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
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
return 0;
This ends the program successfully.