Binary Search Algorithm (eugenp#2452)

techPackets · pivovarit · commit 15666e8ed4bd · 2017-08-23T20:14:49.000+02:00
* Binary search

* deleting previous files

* BinarySearch along with the test case
diff --git a/algorithms/src/main/java/com/baeldung/algorithms/BinarySearch.java b/algorithms/src/main/java/com/baeldung/algorithms/BinarySearch.java
@@ -1,11 +1,11 @@
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
 public class BinarySearch {
 
-    public int runBinarySearch() {
-        int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
-        int key = 6;
+    public int runBinarySearchIteratively(int[] sortedArray, int key, int low, int high) {
 
-        int low = 0;
-        int high = sortedArray.length - 1;
         int index = Integer.MAX_VALUE;
 
         while (low <= high) {
@@ -23,4 +23,31 @@ public int runBinarySearch() {
         }
         return index;
     }
+
+    public int runBinarySearchRecursively(int[] sortedArray, int key, int low, int high) {
+
+        int middle = (low + high) / 2;
+        if (high < low) {
+            return -1;
+        }
+
+        if (key == sortedArray[middle]) {
+          return middle;
+        } else if (key < sortedArray[middle]) {
+          return runBinarySearchRecursively(sortedArray, key, low, middle - 1);
+        } else {
+          return runBinarySearchRecursively(sortedArray, key, middle + 1, high);
+        }
+    }
+
+    public int runBinarySearchUsingJavaArrays(int[] sortedArray, Integer key) {
+        int index = Arrays.binarySearch(sortedArray, key);
+        return index;
+    }
+
+    public int runBinarySearchUsingJavaCollections(List<Integer> sortedList, Integer key) {
+        int index = Collections.binarySearch(sortedList, key);
+        return index;
+    }
+
 }
diff --git a/algorithms/src/test/java/algorithms/BinarySearchTest.java b/algorithms/src/test/java/algorithms/BinarySearchTest.java
@@ -1,14 +1,41 @@
+import java.util.Arrays;
+import java.util.List;
+
 import org.junit.Assert;
 import org.junit.Test;
 
 
 public class BinarySearchTest {
 
+    int[] sortedArray = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9 };
+    int key = 6;
+    int expectedIndexForSearchKey = 7;
+    int low = 0;
+    int high = sortedArray.length - 1;
+    List<Integer> sortedList = Arrays.asList(0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 9, 9);
+    
     @Test
-    public void givenASortedArrayOfIntegers_whenBinarySearchRunForANumber_thenGetIndexOfTheNumber() {
+    public void givenASortedArrayOfIntegers_whenBinarySearchRunIterativelyForANumber_thenGetIndexOfTheNumber() {
         BinarySearch binSearch = new BinarySearch();
-        int expectedIndexForSearchKey = 7;
-        Assert.assertEquals(expectedIndexForSearchKey, binSearch.runBinarySearch());
+        Assert.assertEquals(expectedIndexForSearchKey, binSearch.runBinarySearchIteratively(sortedArray, key, low, high));
     }
 
+    @Test
+    public void givenASortedArrayOfIntegers_whenBinarySearchRunRecursivelyForANumber_thenGetIndexOfTheNumber() {
+        BinarySearch binSearch = new BinarySearch();
+        Assert.assertEquals(expectedIndexForSearchKey, binSearch.runBinarySearchRecursively(sortedArray, key, low, high));
+    }
+    
+    @Test
+    public void givenASortedArrayOfIntegers_whenBinarySearchRunUsingArraysClassStaticMethodForANumber_thenGetIndexOfTheNumber() {
+        BinarySearch binSearch = new BinarySearch();
+        Assert.assertEquals(expectedIndexForSearchKey, binSearch.runBinarySearchUsingJavaArrays(sortedArray, key));
+    }
+    
+    @Test
+    public void givenASortedListOfIntegers_whenBinarySearchRunUsingCollectionsClassStaticMethodForANumber_thenGetIndexOfTheNumber() {
+        BinarySearch binSearch = new BinarySearch();
+        Assert.assertEquals(expectedIndexForSearchKey, binSearch.runBinarySearchUsingJavaCollections(sortedList, key));
+    }
+    
 }
