jump_search.c
searching Implementation
48 lines1142 bytesC
1#include <stdio.h>
2#include <math.h>
3
4// Function to perform Jump Search
5int jumpSearch(int arr[], int n, int x) {
6 // Finding block size to be jumped
7 int step = sqrt(n);
8 int prev = 0;
9
10 // Finding the block where element is present (if it is present)
11 while (arr[(int)fmin(step, n) - 1] < x) {
12 prev = step;
13 step += sqrt(n);
14 if (prev >= n)
15 return -1;
16 }
17
18 // Doing a linear search for x in block beginning with prev
19 while (arr[prev] < x) {
20 prev++;
21 // If we reached next block or end of array, element is not present.
22 if (prev == fmin(step, n))
23 return -1;
24 }
25
26 // If element is found
27 if (arr[prev] == x)
28 return prev;
29
30 return -1;
31}
32
33int main() {
34 int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 };
35 int x = 55;
36 int n = sizeof(arr) / sizeof(arr[0]);
37
38 // Find the index of 'x' using Jump Search
39 int index = jumpSearch(arr, n, x);
40
41 if (index != -1)
42 printf("Number %d found at index %d\n", x, index);
43 else
44 printf("Number %d not found\n", x);
45
46 return 0;
47}
48