Search an array A of integers of size N for a VAL value entered on the keyboard. Display the position of VAL if it is in the array, otherwise display a corresponding message. The INDEX value that is used to memorize the position of the value in the array, will have the value -1 as long as VAL was not found.

The Jump Search is a searching algorithm for sorted arrays. The basic idea is to jump ahead by fixed steps (usually sqrt(N)).

For the above array, we search indexed, A[0],  A[sqrt(N)], A[2*sqrt(N)] ,..
Once we find the interval (A[k*sqrt(N)]< VAL < A[(k+1)*sqrt(N)]), apply a linear search operation from the index k*sqrt(N) to find VAL.

#include<stdio.h>
#include<conio.h>
#include<math.h>
#define SIZE 50
void main()
{
	int A[SIZE], N, val;
	int i;
	int block, min, previous, flag;

	do {
		printf("Enter the dimension: ");
		scanf("%d", &N);
	} while (N <= 0 || N > SIZE);


	// reading the array in ascending order
	printf("Enter A[0]: ");
	scanf("%d", &A[0]);
	for (i = 1; i < N; i++)
	{
		do{
			printf("Enter A[%d]: ", i);
			scanf("%d", &A[i]);
		}while(A[i]<A[i-1]);
	}

	printf("Enter the element to find: ");
	scanf("%d", &val);


 	/* Display the array */
 	printf("Given array : \n");
 	for (i=0; i<N; i++)
    		printf("A[%d]=%d\n",i, A[i]);
 	printf("\n");


 	/* Initializing the number of steps */
	// for jump sort, the block size if best equal to sqrt(N)
	// example, for an array of size 16, the block size is equal to 4
 	block=sqrt(N);
	// we check A[block] , we make sure that block is not out of bound
	flag=1;
	while(flag==1)
	{
		// get the min between step and N
		min = (block<N? block:N);
		// if current value is less than val
		if(A[min-1]< val)
		{
			// save the position of step, we can get
			// back to it, in the case where the 
			// upcoming value at the netx step is 
			// greater than val
			previous=block;
			if(previous>=N)
				flag=0;
			block+= sqrt(N); // increment the step by block size
		}
		else
			break;
	}
	if(flag)
	{
		// we do here a linera search
		// we start from previous index
		while(A[previous]< val && flag)
		{
			previous++;
			// if we reach the next block or 
			// the end of the array, val is missing
			min = (block<N? block:N);
			if(previous==min)
				flag=0;
		}
	}

	// I can reach here with either flag equal to 0 or 1
	// in case where flag=1 , there's a possibility
	// that the last loop condition was false
	// because A[previous]> val
 	if (flag && A[previous]==val)
     		printf("%d is found at index %d.\n", val, previous);
	else
     		printf("%d not found in the array.\n", val);

	getch();
}