Jump search

public class Main 
{ 
    //Custom impl worst O(n^2)
    public static int jumpSearch(int[] arr, int x) 
    { 
        int n = arr.length; 
        int step = (int)Math.floor(Math.sqrt(n)); 
        int prev = 0; 
        while (arr[Math.min(step, n)-1] < x) { 
            prev = step; 
            step += (int)Math.floor(Math.sqrt(n)); 
            if (prev >= n) 
                return -1; 
        } 
        while (arr[prev] < x)  { 
            prev++; 
            if (prev == Math.min(step, n)) 
                return -1; 
        } 
        if (arr[prev] == x) 
            return prev; 
        return -1; 
    } 
    
    //My impl worst O(n^2)
    public static int findFirstIndexOf(int[] arr, int el) {
        int stepSize = (int) Math.round(Math.sqrt((double) arr.length));
        int i = 0;
        while (el > arr[i]) {
            i = i + stepSize;
        }
        if (i < stepSize) {
            for (int j = i; j <= arr.length-1; j++) {
                if (arr[j] == el) return j;
            }
        } else {
            for (int j = i - stepSize; j <= el; j++) {
                if (arr[j] == el) return j;
            }
        }
        return -1;
    }
  
    // Driver program to test function 
    public static void main(String [ ] args) 
    { 
        int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 
                    34, 55, 89, 144, 233, 377, 610}; 
        int x = 34; 
  
        // Find the index of 'x' using Jump Search 
        int index = jumpSearch(arr, x);
        int index2 = findFirstIndexOf(arr, x);
  
        // Print the index where 'x' is located 
        System.out.println("\nNumber " + x + 
                            " is at index " + index + " or " + index2); 
    } 
}