Search Algorithm using Java — 3
In this article we will get to know about Jump Search.
3. Jump Search
Like binary search, jump search is a searching algorithm for sorted arrays. It works by first searching all items until an item is found that is larger than the search key. To find the exact position of the search key in the list a linear search is formed on the sublist. Jump search is better than linear search but worse than a binary search. The optimal value step size(m) is √n.
Lets consider this
arr[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610}
length of the array = 16;
we will find 55;
jump size (m) = √n ; √16 = 4;
Step 1 : jump from index 0 to index 4;
Step 2 : jump from index 4 to index 8;
Step 3 : jump from index 8 to index 12.
Step 4 : Since the element at index 12 is greater than 55, we will jump back a step to come to index 8.
Step 5 : Perform linear search from index 8 to get the element 55.
Jump Search Example Code
public class JumpSearch {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.println(“enter the array size”);
int arr_size = scanner.nextInt();
int[] arr = new int[arr_size];
System.out.println(“enter the array element”);
for (int i = 0; i < arr.length; i++){
arr[i] = scanner.nextInt();
}
System.out.println(“Enter search element”);
int search_element = scanner.nextInt();
int result = jumpSearch(arr, search_element);
if (result == -1){
System.out.println(“element not available”+result);
}else{
System.out.println(“index of element is “+result);
}
scanner.close();
}
private static int jumpSearch(int[] arr, int x) {
int arr_size = arr.length;
int prev = 0;
int step = (int) Math.floor(Math.sqrt(arr_size));
while (arr[Math.min(step, arr_size) — 1] < x){
prev = step; step += (int) Math.floor(Math.sqrt(arr_size));
if (prev >= arr_size){
return -1;
}
while(arr[prev] < x){
prev++;
if (prev == Math.min(step, arr_size)) return -1;
}
if (arr[prev] == x){
return prev;
}
}
return -1;
}
}
GitHub link for Jump search code.
Follow me on GitHub for more data structure and algorithm practice.
In the next article we will get to know about Interpolation Search.
