Java/Searches/JumpSearch.java at dev · primary-code-test/Java · GitHub

Repository navigation

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 */

}