Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Fibonacci search by Henry Kroll III www.thenerdshow.com
Language:
Ada
Assembly
Bash
C#
C++ (gcc)
C++ (clang)
C++ (vc++)
C (gcc)
C (clang)
C (vc)
Client Side
Clojure
Common Lisp
D
Elixir
Erlang
F#
Fortran
Go
Haskell
Java
Javascript
Kotlin
Lua
MySql
Node.js
Ocaml
Octave
Objective-C
Oracle
Pascal
Perl
Php
PostgreSQL
Prolog
Python
Python 3
R
Rust
Ruby
Scala
Scheme
Sql Server
Swift
Tcl
Visual Basic
Layout:
Vertical
Horizontal
//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; }
clang
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
fork mode
|
history
|
discussion