package InfinityJune21.SearchTechniques;

public class JumpSearch {

public static int jumpSearch(int arr[], int key) {

int length = arr.length;

int step = (int)Math.sqrt(length);

int prev = 0;

while(arr[Math.min(step, length) - 1] < key) {

prev = step;

step = step + (int)Math.sqrt(length);

if(prev >= length) {

return -1;

}

}

while(arr[prev] < key) {

prev++;

if(prev == (Math.min(step, length)) - 1) {

return -1;

}

}

if(arr[prev] == key) {

return prev;

}

return -1;

}

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 key = 1;

int index = jumpSearch(arr, key);

if(index != -1) {

System.out.println("Element found at index " + index);

}

else {

System.out.println("Element not found");

}

}

}