Fibonacci Search
Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers. Compared to binary search where the sorted array is divided into two equalsized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers.
Implementation in various languages: here
You can contribute too!
Complexity  Notation 

Worst case time complexity  O(log n) 
Average case time complexity  O(log n) 
Best case time complexity  O(1) 
Average space complexity  O(1) 
Algorithm
Given a table of records R1, R2, …, RN whose keys are in increasing order K1 < K2 < … < KN, the algorithm searches for a given argument K. Assume N+1 = Fk+1

Step 1. [Initialize] i ← Fk, p ← Fk1, q ← Fk2 (throughout the algorithm, p and q will be consecutive Fibonacci numbers)

Step 2. [Compare] If K < Ki, go to Step 3; if K > Ki go to Step 4; and if K = Ki, the algorithm terminates successfully.

Step 3. [Decrease i] If q=0, the algorithm terminates unsuccessfully. Otherwise set (i, p, q) ← (p, q, p  q) (which moves p and q one position back in the Fibonacci sequence); then return to Step 2

Step 4. [Increase i] If p=1, the algorithm terminates unsuccessfully. Otherwise set (i,p,q) ← (i + q, p  q, 2q  p) (which moves p and q two positions back in the Fibonacci sequence); and return to Step 2
Continue the discussion in the comments.