Added binary search and test

varunu28 · varunu28 · commit 90a4c3661881 · 2018-08-25T08:39:01.000-07:00
diff --git a/.gitignore b/.gitignore
@@ -1,2 +1,4 @@
 Java.iml
+.idea/*
 out/
+Downloads.iml
diff --git a/src/main/com/java/search/BinarySearch.java b/src/main/com/java/search/BinarySearch.java
@@ -0,0 +1,49 @@
+package src.main.com.java.search;
+
+/**
+ * Binary search is an algorithm which finds the position of a target value within a sorted array
+ *
+ * Worst-case performance	O(log n)
+ * Best-case performance	O(1)
+ * Average performance	O(log n)
+ * Worst-case space complexity	O(1)
+ */
+public class BinarySearch {
+
+    /**
+     * @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 index of the element
+     */
+    public <T extends Comparable<T>> int findIndex(T array[], T key) {
+        return search(array, key, 0, array.length-1);
+    }
+
+    /**
+     * @param array The array to make the binary search
+     * @param key The number you are looking for
+     * @param left The lower bound
+     * @param right The  upper bound
+     * @return the location of the key
+     **/
+    private <T extends Comparable<T>> int search(T array[], T key, int left, int right){
+        if (left > right) {
+            return -1; // Key not found
+        }
+
+        // Find median
+        int median = (left + right)/2;
+        int comp = key.compareTo(array[median]);
+
+        if (comp < 0) {
+            return search(array, key, left, median - 1);
+        }
+
+        if (comp > 0) {
+            return search(array, key, median + 1, right);
+        }
+
+        return median;
+    }
+}
diff --git a/src/test/com/java/search/BinarySearchTest.java b/src/test/com/java/search/BinarySearchTest.java
@@ -0,0 +1,24 @@
+package src.test.com.java.search;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.com.java.search.BinarySearch;
+
+public class BinarySearchTest {
+
+    @Test
+    public void testBinarySearch() {
+        BinarySearch binarySearch = new BinarySearch();
+
+        Integer[] arr1 = {1,2,3,4,5};
+        Assert.assertEquals("Incorrect index", 2, binarySearch.findIndex(arr1,3));
+        Assert.assertEquals("Incorrect index", 0, binarySearch.findIndex(arr1,1));
+        Assert.assertEquals("Incorrect index", -1, binarySearch.findIndex(arr1,8));
+        Assert.assertEquals("Incorrect index", -1, binarySearch.findIndex(arr1,-2));
+
+        String[] arr2 = {"A", "B", "C", "D"};
+        Assert.assertEquals("Incorrect index", 2, binarySearch.findIndex(arr2,"C"));
+        Assert.assertEquals("Incorrect index", 1, binarySearch.findIndex(arr2,"B"));
+        Assert.assertEquals("Incorrect index", -1, binarySearch.findIndex(arr2,"F"));
+    }
+}

-Original file line number
+Diff line change
@@ @@ -1,2 +1,4 @@ @@
 Java.iml
 +.idea/*
 out/
 +Downloads.iml