Fibonacci search by Henry Kroll III www.thenerdshow.com, C (clang)

Language: Layout:

//Fibonacci search Copyright(C) 2016 Henry Kroll III www.thenerdshow.com
#include <stdio.h>
#include <string.h>
//sorted word list
char *lsit[] ={ "1","10–13","1kg","20-50","2050.","550bn",
"a","about","add","amount","and","as","by","carnivorous",
"consumer","could","crops","cubic","demand","diets","extra",
"food","for","globally","growing","in","is","it","kilogram",
"meat","metres","never","of","pressure","produce","production",
"reach","takes","than","that","the","times","to","trillion",
"vegetables","wasted","water","year", NULL};
//list length function
int len (char **l) {
    int i=0;while (l[i++]);
    return --i;
}
//Fibonacci number generator
int fib (int n) {
    if (n<2) return 1;
    else return fib(n-1) + fib(n-2);
}
//Fibonacci search
int fibsearch(char **a, char *x) {
    static int f[32]= {0}; 
    //generate fibs on first run
    if (!f[1]) for (int i=0;i<31;i++) f[i+1] = fib(i);
    int kk = -1, nn = -1, inf = 0, pos, k, n = len(a);
    if (nn != n) {
        k = 0; while (f[k] < n) k++;
        kk = k, nn = n;
    } else k = kk;
    while (k) {
        pos = inf + f[--k];
        if ((pos >= n) || (strcmp(x, a[pos]) < 0));
        else if (strcmp(x, a[pos]) > 0) {
            inf = pos + 1, k--;
        } else return pos;
    } return -1;
}
//main
int main (void) {
    int pos[]={14, 27, 7, 42}; //test search string locations
    for (int i=0;i<4;i++) {
        printf ("%12s is at position %i\n",
        lsit[pos[i]], fibsearch(lsit, lsit[pos[i]]));
    } return 0;
}

Show compiler warnings [ + ] Compiler args [ + ] Show input
Compilation time: 0.12 sec, absolute running time: 0.14 sec, cpu time: 0.01 sec, memory peak: 3 Mb, absolute service time: 0,26 sec