FOR FREE YEAR SOLVED

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 = 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.

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.