fibonacci_search.c

searching Implementation

70 lines
2063 bytes
C
1#include <stdio.h>
2
3// Utility function to find minimum of two elements
4int min(int x, int y) { return (x <= y) ? x : y; }
5
6/* Returns index of x if present, else returns -1 */
7int fibMonaccianSearch(int arr[], int x, int n) {
8    /* Initialize fibonacci numbers */
9    int fibMMm2 = 0;   // (m-2)'th Fibonacci No.
10    int fibMMm1 = 1;   // (m-1)'th Fibonacci No.
11    int fibM = fibMMm2 + fibMMm1;  // m'th Fibonacci
12
13    /* fibM is going to store the smallest Fibonacci
14       Number greater than or equal to n */
15    while (fibM < n) {
16        fibMMm2 = fibMMm1;
17        fibMMm1 = fibM;
18        fibM = fibMMm2 + fibMMm1;
19    }
20
21    // Marks the eliminated range from front
22    int offset = -1;
23
24    /* while there are elements to be inspected. Note that
25       we compare arr[fibMm2] with x. When fibM becomes 1,
26       fibMm2 becomes 0 */
27    while (fibM > 1) {
28        // Check if fibMm2 is a valid location
29        int i = min(offset + fibMMm2, n - 1);
30
31        /* If x is greater than the value at index fibMm2,
32           cut the subarray array from offset to i */
33        if (arr[i] < x) {
34            fibM = fibMMm1;
35            fibMMm1 = fibMMm2;
36            fibMMm2 = fibM - fibMMm1;
37            offset = i;
38        }
39        /* If x is greater than the value at index fibMm2,
40           cut the subarray after i+1 */
41        else if (arr[i] > x) {
42            fibM = fibMMm2;
43            fibMMm1 = fibMMm1 - fibMMm2;
44            fibMMm2 = fibM - fibMMm1;
45        }
46        /* element found. return index */
47        else
48            return i;
49    }
50
51    /* comparing the last element with x */
52    if (fibMMm1 && arr[offset + 1] == x)
53        return offset + 1;
54
55    /* element not found. return -1 */
56    return -1;
57}
58
59int main(void) {
60    int arr[] = { 10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100, 235 };
61    int n = sizeof(arr) / sizeof(arr[0]);
62    int x = 85;
63    int ind = fibMonaccianSearch(arr, x, n);
64    if (ind >= 0)
65        printf("Found at index: %d\n", ind);
66    else
67        printf("%d isn't present in the array\n", x);
68    return 0;
69}
70