41 lines
1.1 KiB
Java
41 lines
1.1 KiB
Java
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 */
|
|
}
|
|
}
|