JumpSearch.java

packagecom.thealgorithms.searches;

importcom.thealgorithms.devutils.searches.SearchAlgorithm;

/**
 * An implementation of the Jump Search algorithm.
 *
 * <p>
 * Jump Search is an algorithm for searching sorted arrays. It works by dividing the array
 * into blocks of a fixed size (the block size is typically the square root of the array length)
 * and jumping ahead by this block size to find a range where the target element may be located.
 * Once the range is found, a linear search is performed within that block.
 *
 * <p>
 * The Jump Search algorithm is particularly effective for large sorted arrays where the cost of
 * performing a linear search on the entire array would be prohibitive.
 *
 * <p>
 * Worst-case performance: O(√N)<br>
 * Best-case performance: O(1)<br>
 * Average performance: O(√N)<br>
 * Worst-case space complexity: O(1)
 *
 * <p>
 * This class implements the {@link SearchAlgorithm} interface, providing a generic search method
 * for any comparable type.
 */
publicclassJumpSearchimplementsSearchAlgorithm {

/**
 * Jump Search algorithm implementation.
 *
 * @param array the sorted array containing elements
 * @param key the element to be searched
 * @return the index of {@code key} if found, otherwise -1
 */
@Override
public <TextendsComparable<T>> intfind(T[] array, Tkey) {
intlength = array.length;
intblockSize = (int) Math.sqrt(length);

intlimit = blockSize;
// Jumping ahead to find the block where the key may be located
while (limit < length && key.compareTo(array[limit]) > 0) {
limit = Math.min(limit + blockSize, length - 1);
 }

// Perform linear search within the identified block
for (inti = limit - blockSize; i <= limit && i < length; i++) {
if (array[i].equals(key)) {
returni;
 }
 }
return -1;
 }
}