Implementation of Jump Search in Java

Hello guys, in this tutorial we are going to learn how to implement jump search in Java. This searching algorithm can be applied only on sorted data just like binary search.

In this searching algorithm, we divide the entire array into blocks and then search through these blocks. The length of the blocks depends on the length of the array. Generally, for an array of length n, we take the length of each block to be the square root of n. So, let’s start with the code.

import java.util.Scanner;
import java.lang.Math;
class third
{
  public static void main(String ar[])
  {
   Scanner sc= new Scanner(System.in); 
   System.out.println("Enter size of array:");
   int n=sc.nextInt();
   int a[]=new int[n];
   System.out.println("Enter the elements:");
   for(int i=0;i<n;i++)
   {
     a[i]=sc.nextInt();
   }   
   int block=(int)(Math.sqrt(n));
   System.out.println("Enter the element to search:");
   int x=sc.nextInt();
   if(x>a[n-1] || x<a[0])
   {
     System.out.println("Element does not exist");
     return;
   }
   int i=0;
   int j=block;
   while(a[j]<x && j<n)
   {
    i=j;
    j=j+block; 
    if(j>n-1)
    {
     j=n-1;
    }
   
   }
   for(int k=i;k<=j;k++)
    {
      if(a[k]==x)
       {
        System.out.println("Element found at position:"+(k+1));
         return;
       }
    }
   System.out.println("Element doesn't exist");
   
  }
}

Java program to implement Jump Search

First, we take the input from the user using Scanner class.

For this, we need to import the Scanner class. We will also need to import Math class from the lang package to use the sqrt() method for calculating the block of the length.

import java.util.Scanner;
import java.lang.Math;

then, we create object sc of Scanner class. After that, we take input from the user. First, we take the size of the array n and then the actual array elements(remember, that elements must be sorted) and store them in an array named a.

public static void main(String ar[])
  {
   Scanner sc= new Scanner(System.in); 
   System.out.println("Enter size of array:");
   int n=sc.nextInt();
   int a[]=new int[n];
   System.out.println("Enter the elements:")
   for(int i=0;i<n;i++)
   {
     a[i]=sc.nextInt();
   }

Now, the actual searching begins

We will start by finding the length of each block. We create a variable named block and set it to the square root of the size of the array n entered by the user. Then, input the element to search and store it in the variable named x.

int block=(int)(Math.sqrt(n));
   System.out.println("Enter the element to search:");
   int x=sc.nextInt();

Now, first check whether the element to search within the range of array entered by the user using if statement. If not, then return by saying the element does not exist. Otherwise, we proceed forward.

if(x>a[n-1] || x<a[0])
   {
     System.out.println("Element does not exist");
     return;
   }

Now, take two variables i, j, and set i=0, j=block. Then, start a loop which will keep iterating until a[j]<x and j<n. And during each iteration, we keep incrementing both, i=j and j=j+block. And for some case, if j>n-1 then we set j=n-1. After the termination of the loop, we will get a particular block in which the element may exist.

int i=0;
int j=block;
while(a[j]<x && j<n)
{
 i=j;
 j=j+block; 
 if(j>n-1)
 {
  j=n-1;
 }
}

Now, we know that the element to be found may exist in between the range i and j. So, we perform a linear search in the range from i to j. If found then print the position of the element and return. Otherwise, return by saying that element doesn’t exist.

Output:

Enter size of array:
5
Enter the elements:
1
2
3
4
5
Enter the element to search:
5
Element found at position:5

Also read: Searching in a sorted and rotated array using Java

Leave a Reply

Your email address will not be published. Required fields are marked *