Interpolation search
Given a sorted integer array and a target, determine if the target exists in the array or not using an interpolation search algorithm. If the target exists in the array, return the index of it.
For example,
arr[] = [2, 3, 5, 7, 9]
target = 7
Output: Element found at index 3
Input:
arr[] = [1, 4, 5, 8, 9]
target = 2
Output: Element not found
Interpolation search is an algorithm similar to binary search for searching for a given target value in a sorted array. It parallels how humans search through a telephone book for a particular name, the target value by which the book’s entries are ordered.
We know that binary search always chooses the middle of the remaining search space, discarding one half or the other depending on the comparison result between the mid-value and the target value. The remaining search space is reduced to the part before or after the mid-position.
By comparison, at each search step, Interpolation search calculates wherein the remaining search space the target might be present, based on the low and high values of the search space and the target’s value. The value found at this estimated position is then compared to the target value. If it’s not equal, then the remaining search space is reduced to the part before or after the estimated position depending on the comparison. This method will only work if calculations on the size of differences between target values are sensible.
Interpolation search uses the following formula to calculate the mid-position where A[low…high] is our search space, and target is the given target:
Following is the C, Java, and Python implementation of interpolation search. It computes a mid-position at each iteration and then, as with the binary search, moves either the upper or lower bound in to define a smaller interval containing the target value. Unlike the binary search, which guarantees half search space size with each iteration, a poor interpolation may reduce/increase the mid-index by only one, resulting in a worst-case efficiency of O(n) for an input containing n items.
C
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <stdio.h> // Function to determine if target exists in a sorted array `A` or not // using an interpolation search algorithm int interpolationSearch(int A[], int n, int target) { // base case if (n == 0) { return -1; } // search space is A[low…high] int low = 0, high = n - 1, mid; while (A[high] != A[low] && target >= A[low] && target <= A[high]) { // estimate mid mid = low + ((target - A[low]) * (high - low) / (A[high] - A[low])); // target value is found if (target == A[mid]) { return mid; } // discard all elements in the right search space, including the middle element else if (target < A[mid]) { high = mid - 1; } // discard all elements in the left search space, including the middle element else { low = mid + 1; } } // if a target is found if (target == A[low]) { return low; } // target doesn't exist in the array else { return -1; } } int main(void) { int A[] = {2, 5, 6, 8, 9, 10}; int target = 5; int n = sizeof(A)/sizeof(A[0]); int index = interpolationSearch(A, n, target); if (index != -1) { printf("Element found at index %d", index); } else { printf("Element not found in the array"); } return 0; } |
Output:
Element found at index 1
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
class Main { // Function to determine if target exists in a sorted array `A` or not // using an interpolation search algorithm public static int interpolationSearch(int[] A, int target) { // base case if (A == null || A.length == 0) { return -1; } // search space is A[left…right] int left = 0; int right = A.length - 1; while (A[right] != A[left] && target >= A[left] && target <= A[right]) { // estimate mid int mid = left + ((target - A[left])*(right - left)/(A[right] - A[left])); // key is found if (target == A[mid]) { return mid; } // discard all elements in the right search space, including middle element else if (target < A[mid]) { right = mid - 1; } // discard all elements in the left search space, including middle element else { left = mid + 1; } } // if the key is found if (target == A[left]) { return left; } // target doesn't exist in the array return -1; } public static void main(String[] args) { int[] A = {2, 5, 6, 8, 9, 10}; int key = 5; int index = interpolationSearch(A, key); if (index != -1) { System.out.println("Element found at index " + index); } else { System.out.println("Element not found in the array"); } } } |
Output:
Element found at index 1
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
# Function to determine if target exists in the sorted list `A` or not # using an interpolation search algorithm def interpolationSearch(A, target): # base case if not A: return -1 # search space is A[left…right] (left, right) = (0, len(A) - 1) while A[right] != A[left] and A[left] <= target <= A[right]: # estimate mid mid = left + (target - A[left]) * (right - left) // (A[right] - A[left]) # key is found if target == A[mid]: return mid # discard all elements in the right search space, including the middle element elif target < A[mid]: right = mid - 1 # discard all elements in the left search space, including the middle element else: left = mid + 1 # if the key is found if target == A[left]: return left # target doesn't exist in the list return -1 if __name__ == '__main__': A = [2, 5, 6, 8, 9, 10] key = 5 index = interpolationSearch(A, key) if index != -1: print('Element found at index', index) else: print('Element found not in the list') |
Output:
Element found at index 1
Performance
Each iteration of the above code requires between five and six comparisons. On average, the interpolation search makes about log(log(n)) comparisons if the elements are uniformly distributed, where n is the total number of elements to be searched. In the worst case, it can make up to O(n) comparisons. The worst-case might happen when the numerical values of the targets increase exponentially.
Note: This article doesn’t provide an in-depth analysis of how interpolation search works but aims to provide just an overview of achieving better performance than a binary search algorithm for a sorted array.
References: https://en.wikipedia.org/wiki/Interpolation_search
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)