Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
In this article, we will implement Interpolation Search in C++ using some OOPs concept. But before that we need to have a basic idea and working technique of Interpolation Search.
Table of Contents:
- What is Interpolation Search?
- Advantages and Disadvantages
- Approach to implement in C++ using OPPs concept
- Implementation
- Complete C++ Implementation of Interpolation Search
- Time and Space Complexity
Pre-requisites:
What is Interpolation Search?
Interpolation Search is a searching algorithm to find the target element within a sorted and unifromly distributed array. It is the advanced version of Binary Search searching algorithm, in Binary Search the target key is compared to the middle element in the array and according to that the search range is compressed either to the left of middle element is the target key is smaller than the middle element and vice versa.But in Interpolation Search the search range is compressed according to the value of the target element. If the target element's value is closure to the last element in the array the searching will take place near the end of the array.Similarly, if the target element's value is closure to the first element in the array the searching will take place near the start of the array. Initially the search range is the entire array, then An interpolation formula is used to estimate the position of the target value in the array. The formula uses the value of the target element, the value of the element at the beginning of the search range, and the value of the element at the end of the search range.this process then reccursively takes place until target element is found or search range is exhausted.
ADVANTAGES:
- The space range will be found very nearer to the target element after each iteration(changing of lower and upper indeces).
- Faster than Binary Search.
DISADVANTAGES:
- Array element needs to be distributed equally across the array, which makes Binary Search a better choice against Interpolation Searach.
Approach to implement in C++ using OPPs concept.
- Create a class InterpolationSearch with arr and size as private member variables.
- Define a constructor for the InterpolationSearch class that initializes the arr and size member variables.
- Define a public method search that takes a value x as an argument.
Initialize two indices lo and hi to 0 and size - 1, respectively. - Use a while loop to check if lo is less than or equal to hi and x is between arr[lo] and arr[hi].
- If lo equals hi, check if arr[lo] equals x. If it does, return lo, otherwise return -1 to indicate the value was not found.
- Calculate the position pos of the mid-point in the range between lo and hi using the formula:
pos = lo + ((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]);
Implementation
#include <iostream>
using namespace std;
//creating class
class InterpolationSearch {
private:
int* arr;
int size;
The arr and size are declare as private so they cannot be accessed from outside the class and prevent external code from accidentally modifying the internal state of the class.
//public function
public:
InterpolationSearch(int* arr, int size) {
this->arr = arr;
this->size = size;
}
The interpolationSearch is a public member function so that it can access arr and size and can also be called from outside the class.The this keyword is used to access the values of the arr and size member variables of the current instance of the InterpolationSearch class within the method.
int search(int x) {
int lo = 0, hi = size - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
if (lo == hi) {
if (arr[lo] == x) return lo;
return -1;
}
//interpolation formulae
int pos = lo + ((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]);
//target element found
if (arr[pos] == x) {
return pos;
}
//search range will be shifted near ending of the array
else if (arr[pos] < x) {
lo = pos + 1;
}
//search range will be shifted near starting of the array
else {
hi = pos - 1;
}
}
return -1;
}
};
The search method takes the target element as it's argument and performs the Interpolation Search.Using the formula the search range is decided.
int main() {
int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
int size = sizeof(arr) / sizeof(arr[0]);
//object declaration
InterpolationSearch searchObj(arr, size);
//initialising target element
int x = 16;
int result = searchObj.search(x);
if (result == -1) {
cout << x << " not found" << endl;
}
else {
cout << x << " found at index " << result << endl;
}
return 0;
}
Inside the main function first the declaration and initiaisation of an instance i.e searchObj of the class InterpolationSearch is done.Then the search method of searchObj instance is called and the result is stored in the result variable and acoordingly provides the output.
Output:
16 found at index 7
Complete C++ Implementation of Interpolation Search
Following is the Complete C++ Implementation of Interpolation Search using OOP concepts:
// iq.opengenus.org
#include <iostream>
using namespace std;
//creating class
class InterpolationSearch {
private:
int* arr;
int size;
//public function
public:
InterpolationSearch(int* arr, int size) {
this->arr = arr;
this->size = size;
}
int search(int x) {
int lo = 0, hi = size - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
if (lo == hi) {
if (arr[lo] == x) return lo;
return -1;
}
//interpolation formulae
int pos = lo + ((double)(hi - lo) / (arr[hi] - arr[lo])) * (x - arr[lo]);
//target element found
if (arr[pos] == x) {
return pos;
}
//search range will be shifted near ending of the array
else if (arr[pos] < x) {
lo = pos + 1;
}
//search range will be shifted near starting of the array
else {
hi = pos - 1;
}
}
return -1;
}
};
int main() {
int arr[] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
int size = sizeof(arr) / sizeof(arr[0]);
//object declaration
InterpolationSearch searchObj(arr, size);
//initialising target element
int x = 16;
int result = searchObj.search(x);
if (result == -1) {
cout << x << " not found" << endl;
}
else {
cout << x << " found at index " << result << endl;
}
return 0;
}
Time Complexity And Space Complexity
Time Complexity: O(log log n)[Average Case], O(n)[Worst Case]
Space Complexity: O(1)
With this article at OpenGenus, you must have the complete idea of implementing Interpolation Search in C++.
