Skip to content

Commit d814728

Browse files
yanglbmeyanglbme
authored
Merge pull request #628 from Feconiz/Development
Added Linear Search, changed Binary search
2 parents 7c0c4bc + c6ce36b commit d814728

4 files changed

Lines changed: 76 additions & 14 deletions

File tree

‎src/main/java/com/search/BinarySearch.java‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -8,26 +8,26 @@
88
* Average performance O(log n)
99
* Worst-case space complexity O(1)
1010
*/
11-
public class BinarySearch {
11+
public final class BinarySearch{
1212

1313
/**
1414
* @param array is an array where the element should be found
1515
* @param key is an element which should be found
1616
* @param <T> is any comparable type
1717
* @return index of the element
1818
*/
19-
public <T extends Comparable<T>> int findIndex(T array[], T key) {
19+
public static <T extends Comparable<T>> int findIndex(T array[], T key) {
2020
return search(array, key, 0, array.length-1);
2121
}
2222

2323
/**
24-
* @param array The array to make the binary search
25-
* @param key The number you are looking for
24+
* @param array The array to search
25+
* @param key The element you are looking for
2626
* @param left The lower bound
2727
* @param right The upper bound
2828
* @return the location of the key
2929
**/
30-
private <T extends Comparable<T>> int search(T array[], T key, int left, int right){
30+
private static <T extends Comparable<T>> int search(T array[], T key, int left, int right){
3131
if (left > right) {
3232
return -1; // Key not found
3333
}

‎src/main/java/com/search/LinearSearch.java‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package src.main.java.com.search;
2+
3+
/**
4+
* Linear search is an algorithm which finds the position of a target value within an array (Usually unsorted)
5+
*
6+
* Worst-case performance O(n)
7+
* Best-case performance O(1)
8+
* Average performance O(n)
9+
* Worst-case space complexity O(1)
10+
*/
11+
public final class LinearSearch {
12+
/**
13+
* @param array is an array where the element should be found
14+
* @param key is an element which should be found
15+
* @param <T> is any comparable type
16+
* @return index of the element
17+
*/
18+
public static <T extends Comparable<T>> int findIndex(T array[], T key) {
19+
return search(array, key);
20+
}
21+
22+
/**
23+
* @param array The array to search
24+
* @param key The element you are looking for
25+
* @return the location of the key or -1 if the element is not found
26+
**/
27+
private static <T extends Comparable<T>> int search(T array[], T key){
28+
for(int i = 0; i < array.length;i++) {
29+
if (array[i].compareTo(key) == 0){
30+
return i;
31+
}
32+
}
33+
return -1;
34+
}
35+
}

‎src/test/java/com/search/BinarySearchTest.java‎

Lines changed: 10 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -8,17 +8,18 @@ public class BinarySearchTest {
88

99
@Test
1010
public void testBinarySearch() {
11-
BinarySearch binarySearch = new BinarySearch();
12-
1311
Integer[] arr1 = {1,2,3,4,5};
14-
Assert.assertEquals("Incorrect index", 2, binarySearch.findIndex(arr1,3));
15-
Assert.assertEquals("Incorrect index", 0, binarySearch.findIndex(arr1,1));
16-
Assert.assertEquals("Incorrect index", -1, binarySearch.findIndex(arr1,8));
17-
Assert.assertEquals("Incorrect index", -1, binarySearch.findIndex(arr1,-2));
12+
Assert.assertEquals("Incorrect index", 2, BinarySearch.findIndex(arr1,3));
13+
Assert.assertEquals("Incorrect index", 0, BinarySearch.findIndex(arr1,1));
14+
Assert.assertEquals("Incorrect index", -1, BinarySearch.findIndex(arr1,8));
15+
Assert.assertEquals("Incorrect index", -1, BinarySearch.findIndex(arr1,-2));
1816

1917
String[] arr2 = {"A", "B", "C", "D"};
20-
Assert.assertEquals("Incorrect index", 2, binarySearch.findIndex(arr2,"C"));
21-
Assert.assertEquals("Incorrect index", 1, binarySearch.findIndex(arr2,"B"));
22-
Assert.assertEquals("Incorrect index", -1, binarySearch.findIndex(arr2,"F"));
18+
Assert.assertEquals("Incorrect index", 2, BinarySearch.findIndex(arr2,"C"));
19+
Assert.assertEquals("Incorrect index", 1, BinarySearch.findIndex(arr2,"B"));
20+
Assert.assertEquals("Incorrect index", -1, BinarySearch.findIndex(arr2,"F"));
21+
22+
String[] arr3 = {};
23+
Assert.assertEquals("Incorrect index", -1, BinarySearch.findIndex(arr3, ""));
2324
}
2425
}

‎src/test/java/com/search/LinearSearchTest.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package src.test.java.com.search;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
import src.main.java.com.search.LinearSearch;
6+
7+
public class LinearSearchTest {
8+
@Test
9+
public void testLinearSearch() {
10+
11+
Integer[] arr1 = {1,2,3,4,5};
12+
Assert.assertEquals("Incorrect index", 2, LinearSearch.findIndex(arr1,3));
13+
Assert.assertEquals("Incorrect index", 0, LinearSearch.findIndex(arr1,1));
14+
Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr1,8));
15+
Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr1,-2));
16+
17+
String[] arr2 = {"A", "B", "C", "D"};
18+
Assert.assertEquals("Incorrect index", 2, LinearSearch.findIndex(arr2,"C"));
19+
Assert.assertEquals("Incorrect index", 1, LinearSearch.findIndex(arr2,"B"));
20+
Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr2,"F"));
21+
22+
String[] arr3 = {};
23+
Assert.assertEquals("Incorrect index", -1, LinearSearch.findIndex(arr3, ""));
24+
25+
}
26+
}

0 commit comments

Comments
 (0)