title: Fibonacci Search
body: <p>Somebody please explain me the fibonacci search algorithm.</p>
  
  <p>I have tried numerous resources around and searched a lot, but the algorithm is still unclear. Most of the resources described it in link with binary search, but I didn't understand 'em. I know fibonacci search algorithm is an extension of binary search, which I know quite well.</p>
  
  <p>My books failed to explain as well.</p>
  
  <p>I know about fibonacci numbers defined as F(n) = F(n-1) + F(n-2), so no need to explain that.</p>
  
  <p>Updating the question by adding what exactly I didn't understand as @AnthonyLabarre said:</p>
  
  <p>The book I'm using has strange symbols without any explanations. Posting the algo here, please help.</p>
  
  <pre><code>if(key == a[mid]) return mid; // understood this, comes from binary search
  if(key &gt; a[mid]) {
    if(p == 1) return -1; // What is p? It comes as a function arg
    mid = mid + q; //Now what's this q? Again comes a function arg
    p = p - q; // Commented as p=fib(k-4)
    q = q-p; // q = fib(k-5)
   } else // key &lt; a[mid] {
    if(q == 0) return -1;
    mid = mid - q;
    temp = p - q;
    p = q; // p=fib(k-3)
    q = temp; // q = fib(k-4)
    return fibsearch(a, key, mid, p, q);
  }
  </code></pre>