📘 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
Position Probing in Interpolation Search
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
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);
}
}
Remember array index starts from 0
The size of the array is : 10
The element found at index : 9
Reference
- 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