// jump search program in C
#include<stdio.h>
#include<math.h>
int JumpSearch(int a[], int elem, int sz)
{
int low = 0 ;
int i = 0 ;
int j = sqrt(sz) ;
for (i = 0; i < sz; i += j)
{
// check if arr[i] == elem
if (a[i] == elem)
{
return i;
}
if (a[i] < elem)
{
low = i;
}
if (a[i] > elem)
{
break ;
}
}
// linear search for element from low to end of array
for (i = low; i < sz ; i ++)
{
if (a[i] == elem)
{
return i;
}
}
return -1 ;
}
int main()
{
// take size of array as input
int sz = 0; int i = 0; int j = 0, elem = 0;
int index = 0 ;
printf("Enter size of array : ") ;
scanf("%d", &sz);
// initialize empty array of size sz
int a[sz] ;
// input elements into array, sorted order
for (i = 0; i < sz; i++)
{
printf("enter element at positions %d : ", i+1);
scanf("%d", &a[i]) ;
}
// get element to search
printf("enter element to search for in th earray : ") ;
scanf("%d", &elem) ;
// find index of element
index = JumpSearch(a, elem, sz) ;
if (index == -1)
{
printf("sorry, element not found within the array.\n") ;
}
else
{
printf("element found at positions %d\n", index + 1);
}
return 0 ;
}