Jump search algorithm

jumpSearch.java

public static int jumpSearch(int[] array, int target) {
    int currentRight = 0; // right border of the current block
    int prevRight = 0; // right border of the previous block
 
    /* If array is empty, the element is not found */
    if (array.length == 0) {
        return -1;
    }
 
    /* Check the first element */
    if (array[currentRight] == target) {
        return 0;
    }
 
    /* Calculating the jump length over array elements */
    int jumpLength = (int) Math.sqrt(array.length);
 
    /* Finding a block where the element may be present */
    while (currentRight < array.length - 1) {
 
        /* Calculating the right border of the following block */
        currentRight = Math.min(array.length - 1, currentRight + jumpLength);
 
        if (array[currentRight] >= target) {
            break; // Found a block that may contain the target element
        }
 
        prevRight = currentRight; // update the previous right block border
    }
 
    /* If the last block is reached and it cannot contain the target value => not found */
    if ((currentRight == array.length - 1) && target > array[currentRight]) {
        return -1;
    }
 
    /* Doing linear search in the found block */
    return backwardSearch(array, target, prevRight, currentRight);
}
 
public static int backwardSearch(int[] array, int target, int leftExcl, int rightIncl) {
    for (int i = rightIncl; i > leftExcl; i--) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

recursiveJumpSearch.java

public class Main {
    public static void main(String[] args) {

        int[] arr = {10, 13, 19, 20, 24, 26, 30, 34, 35};
        System.out.println(jumpSearch(arr, 26));

    }

    public static int jumpSearch(int[] arr, int val) {
        int low = 0, high = arr.length - 1;

        while (high - low > 1) {
            Pair p = jumpSearchUtil(arr, val, low, high);

            if (p == null) {
                return -1;
            }

            low = p.left;
            high = p.right;
        }

        if (arr[low] == val) {
            return low;
        } else {
            if (arr[high] == val) return high;
            return -1;
        }
    }

    private static Pair jumpSearchUtil(int[] arr, int val, int low, int high) {
        int left = low;
        int step = (int) Math.sqrt(high - low);
        int right = 0;

        while (left < high && arr[left] <= val) {
            right = Math.min(left + step, high);

            if (arr[left] <= val && arr[right] >= val) {
                return new Pair(left, right);
            }

            left = right;
        }

        return null;
    }
}

class Pair {
    int left, right;

    public Pair(int left, int right) {
        this.left = left;
        this.right = right;
    }

}