Merge pull request TheAlgorithms#652 from LesliePinto89/Development

varunu28 · web-flow · commit 233f05d862f0 · 2019-03-11T07:15:49.000-07:00
Added Jump Search algorithm and JUnit test
diff --git a/src/main/java/com/search/JumpSearch.java b/src/main/java/com/search/JumpSearch.java
@@ -0,0 +1,84 @@
+package src.main.java.com.search;
+
+public class JumpSearch {
+
+	/**
+	 * A jump search algorithm that finds the position of a key by moving over
+	 * fixed block ranges in a sorted array, and linear searches back on itself to
+	 * find it.
+	 * 
+	 * Worst case time complexity: O(N^(1/2)) - square root n 
+	 * Average case time complexity: O(N^(1/2)) - square root n 
+	 * Worst case Space complexity: O(1)
+	 * 
+	 * @param <T> This is any comparable type
+	 * @param arr This is the array where the element should be found
+	 * @param key This is the element to find in the array
+	 * @return The index of the key in the array
+	 */
+	public <T extends Comparable<T>> int findIndex(T arr[], T key) {
+		return checkCondition(arr, key, arr.length);
+	}
+
+	/**
+	 * @param arrLength The array's length
+	 * @return The index position of the key in the array
+	 */
+	public <T extends Comparable<T>> int checkCondition(T arr[], T key, int arrLength) {
+		int step = (int) Math.floor(Math.sqrt(arrLength)); // Find jump block
+		int previous = 0; // Find block where element is / or not present
+
+		// Use ternary operator to find if step or array length is min value
+		// and then minus the min value by one
+		int minVal = (step < arrLength) ? step - 1 : arrLength - 1;
+
+		String arrayMinValIndexString = arr[minVal].toString();
+		int arrayMinValIndexInt = Integer.parseInt(arrayMinValIndexString);
+		String keyValueString = key.toString();
+		int keyValueInt = Integer.parseInt(keyValueString);
+
+		// Increment next step and previous step in block to find range block
+		while (arrayMinValIndexInt < keyValueInt) {
+			previous = step;
+			step += (int) Math.floor(Math.sqrt(arrLength));
+			if (previous >= arrLength)
+				return -1;
+			minVal = (step < arrLength) ? step - 1 : arrLength - 1;
+			arrayMinValIndexString = arr[minVal].toString();
+			arrayMinValIndexInt = Integer.parseInt(arrayMinValIndexString);
+		}
+		// Get key position in linear search
+		int position = linearSearchBlock(arr, key, step, previous, keyValueInt, arrLength, minVal);
+		return position;
+	}
+
+	/**
+	 * @param step The next block index in the array
+	 * @param previous The previous block index in the array
+	 * @param keyValueInt The key in the format of an integer
+	 * @param minVal The minimum value of either next step or array length 
+	 * @return The index position of the key in the array
+	 */
+	public <T extends Comparable<T>> int linearSearchBlock(T arr[], T key, int step, int previous, int keyValueInt,
+			int arrLength, int minVal) {
+
+		// Linear search starting from previous block forwards.
+		String arrayPositionString = arr[previous].toString();
+		int arrayPositionValue = Integer.parseInt(arrayPositionString);
+		while (arrayPositionValue < keyValueInt) {
+			// If in next block or end of array length, key not in array
+			if (previous == minVal)
+				return -1;
+			previous++;
+			// Update arrayPositionValue in iteration
+			minVal = (step < arrLength) ? step - 1 : arrLength - 1;
+			arrayPositionString = arr[previous].toString();
+			arrayPositionValue = Integer.parseInt(arrayPositionString);
+
+		}
+		// If the key is found
+		if (arrayPositionValue == keyValueInt)
+			return previous;
+		return -1;
+	}
+}
diff --git a/src/test/java/com/search/JumpSearchTest.java b/src/test/java/com/search/JumpSearchTest.java
@@ -0,0 +1,29 @@
+package src.test.java.com.search;
+
+import org.junit.Test;
+import org.junit.Assert;
+
+import src.main.java.com.search.JumpSearch;
+
+public class JumpSearchTest {
+
+	@Test
+	public void testJumpSearch() {
+		JumpSearch jumpSearch = new JumpSearch();
+		
+		Integer arr[] = {11, 15, 16, 29, 36, 40, 42, 52};
+		int x = 36;
+		int index = jumpSearch.findIndex(arr, x);
+		Assert.assertEquals("Incorrect index", 4, index);
+
+	    Integer arrTwo[] = {-210, -190, -180, -160, -130, -120, -100};
+		x = -120;
+		index = jumpSearch.findIndex(arrTwo, x);
+		Assert.assertEquals("Incorrect index", 5, index);
+		
+		String arrString[] = {"101", "122", "136", "165", "225", "251","291"};
+		String stringX = "122";
+		index = jumpSearch.findIndex(arrString, stringX);
+		Assert.assertEquals("Incorrect index", 1, index);
+	}
+}
