Added the algorithm and test for Exponential Search

abhijay94 · abhijay94 · commit 1bf9cf601929 · 2019-05-08T13:51:07.000+05:30
diff --git a/src/main/java/com/search/ExponentialSearch.java b/src/main/java/com/search/ExponentialSearch.java
@@ -0,0 +1,39 @@
+package src.main.java.com.search;
+
+import java.util.Arrays;
+
+/**
+ * Exponential search (also called doubling search or galloping search or Struzik search) is an algorithm which finds
+ * the position of a target value within an array. It works by determining a range that the search key resides in and
+ * performing a binary search within that range
+ * <p>
+ * Worst-case performance	O(n)
+ * Best-case performance	O(1)
+ * Average performance	O(Log n)
+ * Worst-case space complexity	O(Log n)
+ */
+public class ExponentialSearch {
+    /**
+     * @param array is an array where the element should be found
+     * @param key   is an element which should be found
+     * @param <T>   is any comparable type
+     * @return The index position of the key in the array, returns -1 for empty array
+     */
+    public <T extends Comparable<T>> int findIndex(T[] array, T key) {
+        int size = array.length;
+        if(size == 0)
+            return -1;
+        // If the element is present at first position
+        if (array[0] == key)
+            return 0;
+
+        // Find the range for binary search by repeated doubling
+        int i = 1;
+        while (i < size && array[i].compareTo(key) <= 0) {
+            i = i * 2;
+        }
+
+        // Call binary search for the range found
+        return Arrays.binarySearch(array, i / 2, Math.min(i, size), key);
+    }
+}
diff --git a/src/test/java/com/search/ExponentialSearchTest.java b/src/test/java/com/search/ExponentialSearchTest.java
@@ -0,0 +1,31 @@
+package src.test.java.com.search;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.search.ExponentialSearch;
+
+public class ExponentialSearchTest {
+    @Test
+    public void testExponentialSearch() {
+        ExponentialSearch expSearch = new ExponentialSearch();
+
+        Integer[] arr = {11, 14, 23, 29, 36, 40, 42, 52};
+        int x = 36;
+        int index = expSearch.findIndex(arr, x);
+        Assert.assertEquals("Incorrect index", 4, index);
+
+        Integer[] arrTwo = {-210, -190, -180, -160, -130, -120, -100};
+        x = -120;
+        index = expSearch.findIndex(arrTwo, x);
+        Assert.assertEquals("Incorrect index", 5, index);
+
+        String[] arrString = {"101", "122", "136", "165", "225", "251", "291"};
+        String stringX = "122";
+        index = expSearch.findIndex(arrString, stringX);
+        Assert.assertEquals("Incorrect index", 1, index);
+
+        String[] arrThree = {};
+        Assert.assertEquals("Incorrect index", -1, expSearch.findIndex(arrThree, ""));
+    }
+
+}
