jump_search.c

searching Implementation

48 lines
1142 bytes
C
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