Interpolation search is an improvement on the binary search algorithm. It differs from binary search in that, instead of choosing the position in the middle of the range being searched, we estimate where the target is likely to fall within that range. In the worst case, interpolation search takes linear time. This worst case occurs only if the assumption of uniform distribution is deeply wrong. On average, interpolation search takes time in O(log (log n)), which is extremely small.
public class InterpolationSearch {
public boolean search(double[] data, double target) {
int bottom = 0;
int top = data.length - 1;
while (bottom <= top) {
double lo = data[bottom];
double hi = data[top];
if (lo == hi) {
return target == lo;
}
if ((target hi)) {
return false;
}
double fraction = (target - lo) / (hi - lo);
int midpoint = bottom + (int) ((top - bottom) * fraction);
System.out.println(midpoint);
if (target < data[midpoint]) {
top = midpoint - 1;
} else if (target == data[midpoint]) {
return true;
} else {
bottom = midpoint + 1;
}
}
return false;
}
public static void main(String[] args) {
double[] data=new double[]{4,8,15,16,23,42};
System.out.println(new InterpolationSearch().search(data, 23));
}
}
