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);
}
}
