Interpolation Search
Interpolation Search Algorithm in C++ (Complete Implementation)
C++ Interpolation Search Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#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;
}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
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:
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
This header provides:
---
#include <iostream>3. Understanding Interpolation Search
Algorithm Concept
:
Visual Example
:
---
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 -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;
}
return left;How it works
:
---
5. Understanding Interpolation Formula
Formula
:
pos = left + ((right - left) / (arr[right] - arr[left])) * (key - arr[left])
How it works
:
Example
(searching for 18):
---
6. Step-by-Step Algorithm
Step 1: Initialize Interval
Step 2: Calculate Position
Step 3: Compare
Step 4: Repeat
---
7. Time and Space Complexity
Time Complexity
:
Space Complexity
: O(1)
---
8. When to Use Interpolation Search
Best For
:
Not Recommended For
:
---
9. Comparison with Binary Search
Interpolation Search Advantages
:
Interpolation Search Disadvantages
:
Binary Search Advantages
:
---
10. Important Considerations
Uniform Distribution Requirement
:
Bounds Checking
:
Position Calculation
:
---
11. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for learning advanced search algorithms, understanding interpolation techniques, and preparing for performance-optimized searching in C++ programs.
Let us now understand every line and the components of the above program.
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.
Practical Learning Notes for Interpolation Search
This C++ program is part of the "Sorting & Searching Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.