InterpolationSearch (eugenp#7575)

afshar-mohammad · maibin · commit d84f97cf7e4c · 2019-08-16T08:04:45.000+02:00
diff --git a/algorithms-miscellaneous-3/src/main/java/com/baeldung/algorithms/interpolationsearch/InterpolationSearch.java b/algorithms-miscellaneous-3/src/main/java/com/baeldung/algorithms/interpolationsearch/InterpolationSearch.java
@@ -0,0 +1,35 @@
+package com.baeldung.algorithms.interpolationsearch;
+
+public class InterpolationSearch {
+
+    public static int interpolationSearch(int[] data, int item) {
+
+        int highEnd = (data.length - 1);
+        int lowEnd = 0;
+
+        while (item >= data[lowEnd] && item <= data[highEnd] && lowEnd <= highEnd) {
+
+            int probe = lowEnd + (highEnd - lowEnd) * (item - data[lowEnd]) / (data[highEnd] - data[lowEnd]);
+
+            if (highEnd == lowEnd) {
+                if (data[lowEnd] == item) {
+                    return lowEnd;
+                } else {
+                    return -1;
+                }
+            }
+
+            if (data[probe] == item) {
+                return probe;
+            }
+
+            if (data[probe] < item) {
+                lowEnd = probe + 1;
+            } else {
+                highEnd = probe - 1;
+            }
+        }
+        return -1;
+    }
+
+}
diff --git a/algorithms-miscellaneous-3/src/test/java/com/baeldung/algorithms/interpolationsearch/InterpolationSearchUnitTest.java b/algorithms-miscellaneous-3/src/test/java/com/baeldung/algorithms/interpolationsearch/InterpolationSearchUnitTest.java
@@ -0,0 +1,29 @@
+package com.baeldung.algorithms.interpolationsearch;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+
+import org.junit.Before;
+import org.junit.Test;
+
+public class InterpolationSearchUnitTest {
+    
+    private int[] myData;
+
+    @Before
+    public void setUp() {
+        myData = new int[]{13,21,34,55,69,73,84,101};
+    }
+    
+    @Test
+    public void givenSortedArray_whenLookingFor84_thenReturn6() {
+        int pos = InterpolationSearch.interpolationSearch(myData, 84);
+        assertEquals(6, pos);
+    }
+    
+    @Test
+    public void givenSortedArray_whenLookingFor19_thenReturnMinusOne() {
+        int pos = InterpolationSearch.interpolationSearch(myData, 19);
+        assertEquals(-1, pos);
+    }
+
+}
