FOR FREE YEAR SOLVED

Jump Search

Back to Programming

Description

The jump search is a searching algorithm that is applicable for the sorted arrays. The idea is to check fewer elements than the linear search by jumping a fixed length or steps by skipping some elements instead of searching all elements.

If the size of the list is n and the block size is m, then the elements array [0], array[m], array[2m] …. Array[km] and so on. If we get the interval as (array[km] < x < array[(k+1) m]), the linear search is performed from the index km to find the element x.

EXAMPLE:

Let the array will be:

The length of the array is 6.

So, the block size = $\sqrt{6}$ = 2

Let the element to be searched is 74.

Now it will jump from index 0 to index 0+2=2.

The searched element is 74 which will be compared with 61(the value at index 2). As 74 is greater than the value of index 2 i.e. 61 then the index will again jump from 2 to 2+2=4.

The searched element is 74 which is lesser than the value at index 4 i.e. 84 then again, the index will jump back to 2. Now the linear search will be performed from the index 2+1=3. The element will be compared with 74.

As the element matched, it will print the position of the element in the array.

Algorithm

INPUT: Array elements
OUTPUT: the position of the element if found
PROCESS:
Step 1: [taking the input]
	Read n [number of elements]
	For i=0 to n-1 repeat
		Read a[i]
	[end of ‘for’ loop]
	Read x [the element which is to be searched]
Step 2: [searching the element]
	Set f<-0
	Set strt <- 0
Set end <-square root of n
    	While a[end]≤ x and end < n repeat
      		Set strt<-end 
      		Set end=end + square root of n
      		If end > n – 1 then
         			Set end<-n 
   		[End of ‘if’]
	[End of ‘while’ loop]
	For i = strt to end-1 repeat
	      If a[i] = x then
      		Print "The element x is found at index i”
      		Set f<-1
	  [End of ‘if’]
   	[End of ‘for’ loop]

 	  If f=0 then
   		Print "element not found"
	[End of ‘if’]	 
Step 3: Stop.

Code

ADVANTAGES:

It requires less comparison than linear search.
In jump search the back traversing is done only once which is lesser than binary search.
In case of a system, in which binary search is costly, jump search is used.

DISADVANTAGES:

It works only on the sorted arrays.
It is less efficient than the binary search algorithm.

TIME COMPLEXITY:

For n number of elements, the best block size is $\sqrt{n}$ which makes the time complexity of the jump search O ( $\sqrt{n}$ ). The complexity of jump search lies between the time complexity of linear search and binary search i.e. O (n) and O( $\log_{2} (n)$ ) respectively.

Please Login to Bookmark