Merge pull request TheAlgorithms#628 from Feconiz/Development

yanglbme · web-flow · commit d814728210b5 · 2018-12-12T09:45:45.000+08:00
Added Linear Search, changed Binary search
diff --git a/src/main/java/com/search/BinarySearch.java b/src/main/java/com/search/BinarySearch.java
@@ -8,26 +8,26 @@
  * Average performance	O(log n)
  * Worst-case space complexity	O(1)
  */
-public class BinarySearch {
+public final 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) {
+    public static <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 array The array to search
+     * @param key The element 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){
+    private static <T extends Comparable<T>> int search(T array[], T key, int left, int right){
         if (left > right) {
             return -1; // Key not found
         }
diff --git a/src/main/java/com/search/LinearSearch.java b/src/main/java/com/search/LinearSearch.java
@@ -0,0 +1,35 @@
+package src.main.java.com.search;
+
+/**
+ * Linear search is an algorithm which finds the position of a target value within an array (Usually unsorted)
+ *
+ * Worst-case performance	O(n)
+ * Best-case performance	O(1)
+ * Average performance	O(n)
+ * Worst-case space complexity	O(1)
+ */
+public final class LinearSearch {
+    /**
+     * @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 static <T extends Comparable<T>> int findIndex(T array[], T key) {
+        return search(array, key);
+    }
+
+    /**
+     * @param array The array to search
+     * @param key The element you are looking for
+     * @return the location of the key or -1 if the element is not found
+     **/
+    private static <T extends Comparable<T>> int search(T array[], T key){
+        for(int i = 0; i < array.length;i++) {
+            if (array[i].compareTo(key) == 0){
+                return i;
+            }
+        }
+        return -1;
+    }
+}
diff --git a/src/test/java/com/search/BinarySearchTest.java b/src/test/java/com/search/BinarySearchTest.java
@@ -8,17 +8,18 @@ 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));
+        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"));
+        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"));
+
+        String[] arr3 = {};
+        Assert.assertEquals("Incorrect index", -1, BinarySearch.findIndex(arr3, ""));
     }
 }
diff --git a/src/test/java/com/search/LinearSearchTest.java b/src/test/java/com/search/LinearSearchTest.java
@@ -0,0 +1,26 @@
+package src.test.java.com.search;
+
+import org.junit.Assert;
+import org.junit.Test;
+import src.main.java.com.search.LinearSearch;
+
+public class LinearSearchTest {
+    @Test
+    public void testLinearSearch() {
+
+        Integer[] arr1 = {1,2,3,4,5};
+        Assert.assertEquals("Incorrect index", 2, LinearSearch.findIndex(arr1,3));
+        Assert.assertEquals("Incorrect index", 0, LinearSearch.findIndex(arr1,1));
+        Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr1,8));
+        Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr1,-2));
+
+        String[] arr2 = {"A", "B", "C", "D"};
+        Assert.assertEquals("Incorrect index", 2, LinearSearch.findIndex(arr2,"C"));
+        Assert.assertEquals("Incorrect index", 1, LinearSearch.findIndex(arr2,"B"));
+        Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr2,"F"));
+
+        String[] arr3 = {};
+        Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr3, ""));
+
+    }
+}
