Jump Search Algorithm
The Jump Search Algorithm is an efficient search technique used to find a target value within a sorted array. It is an optimization over linear search, where you iterate through every element of the array one by one until the target value is found. Instead of checking every element, the Jump Search Algorithm "jumps" ahead by a specified block size, reducing the number of comparisons required to find the target value. If the value at the jump position is greater than the target value, the algorithm goes back to the previous block and performs a linear search within that block to find the exact position of the target value. The optimal block size is usually the square root of the array length, which minimizes the time complexity of the search algorithm.
The Jump Search Algorithm is particularly useful for larger data sets, as it can significantly reduce the number of comparisons required to find the target value. The time complexity of the Jump Search Algorithm is O(√n), where n is the number of elements in the array, making it faster than linear search (O(n)) but slower than binary search (O(log n)). One key advantage of jump search over binary search is that it can work with data structures that do not support random access, such as linked lists, by simply jumping forward by a certain number of nodes. However, it is worth noting that the Jump Search Algorithm requires the input array to be sorted, as it relies on the order of elements to make informed jumps and comparisons.
package Searches;
public class JumpSearch implements SearchAlgorithm {
public static void main(String[] args) {
JumpSearch jumpSearch = new JumpSearch();
Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
for (int i = 0; i < array.length; i++) {
assert jumpSearch.find(array, i) == i;
}
assert jumpSearch.find(array, -1) == -1;
assert jumpSearch.find(array, 11) == -1;
}
/**
* Jump Search algorithm implements
*
* @param array the array contains elements
* @param key to be searched
* @return index of {@code key} if found, otherwise <tt>-1</tt>
*/
@Override
public <T extends Comparable<T>> int find(T[] array, T key) {
int length = array.length; /* length of array */
int blockSize = (int) Math.sqrt(length); /* block size to be jumped */
int limit = blockSize;
while (key.compareTo(array[limit]) > 0 && limit < array.length - 1) {
limit = Math.min(limit + blockSize, array.length - 1);
}
for (int i = limit - blockSize; i <= limit; i++) {
if (array[i] == key) { /* execute linear search */
return i;
}
}
return -1; /* not found */
}
}
