📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.
✅ Some premium posts are free to read — no account needed. Follow me on Medium to stay updated and support my writing.
🎓 Top 10 Udemy Courses (Huge Discount): Explore My Udemy Courses — Learn through real-time, project-based development.
▶️ Subscribe to My YouTube Channel (172K+ subscribers): Java Guides on YouTube
In this article, we will learn in details about the Interpolation Search algorithm.
Interpolation search is an algorithm for searching for a given key in an indexed array that has been ordered by numerical values assigned to the keys (key values). It parallels how humans search through a telephone book for a particular name, the key value by which the book's entries are ordered.
Position Probing in Interpolation Search
Interpolation search finds a particular item by computing the probe position. Initially, the probe position is the position of the middle most item of the collection.
If a match occurs, then the index of the item is returned. To split the list into two parts, we use the following method −
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list
A[n] = Value stored at index n in the list
If the middle item is greater than the item, then the probe position is again calculated in the sub-array to the right of the middle item. Otherwise, the item is searched in the subarray to the left of the middle item. This process continues on the sub-array as well until the size of subarray reduces to zero.
Runtime complexity of interpolation search algorithm is Ο(log (log n)) as compared to Ο(log n) of Binary Search Algorithm in favorable situations.
Interpolation Search Implemenation in Java
/**
* Interpolation search is an algorithm for searching for a given key in an indexed array.
* @author Ramesh Fadatare
*/
public class InterpolationSearch {
private static int[] sorted = null;
// Assuming the array is sorted
public static final int find(int value, int[] array) {
InterpolationSearch.sorted = array;
try {
return recursiveFind(value, 0, InterpolationSearch.sorted.length - 1);
} finally {
InterpolationSearch.sorted = null;
}
}
private static int recursiveFind(int value, int start, int end) {
if (start == end) {
int lastValue = sorted[start]; // start==end
if (value == lastValue)
return start; // start==end
return Integer.MAX_VALUE;
}
final int mid = start + ((value - sorted[start]) * (end - start)) / (sorted[end] - sorted[start]);
if (mid < 0 || mid > end)
return Integer.MAX_VALUE;
int midValue = sorted[mid];
if (value == midValue)
return mid;
if (value > midValue)
return recursiveFind(value, mid + 1, end);
return recursiveFind(value, start, mid - 1);
}
public static void main(String[] args) {
int[] integers = {10,20,30,40,50,60,70,80,90,100};
//the element that should be found
int key = 100;
InterpolationSearch search = new InterpolationSearch();
int atIndex = search.find(key, integers);
System.out.println("Remember array index starts from 0");
System.out.println("The size of the array is : " + integers.length);
System.out.println("The element found at index : " + atIndex);
}
}
Output:
Remember array index starts from 0
The size of the array is : 10
The element found at index : 9Reference
- https://www.tutorialspoint.com/data_structures_algorithms/interpolation_search_algorithm.htm
- https://en.wikipedia.org/wiki/Interpolation_search
Master in Data Structures and Algorithms in Java
Learn Complete Java Programming on Java Tutorial | Learn Java Programming with Examples
Comments
Post a Comment
Leave Comment