Get this book -> Problems on Array: For Interviews and Competitive Programming

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++.