The Fibonacci Numbers consist of the sequence of integers: F₀ = 0, F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, ... . These are defined recursively by the following formula:

This is a strange algorithm similar to binary search, with almost the same performance. [Fibonacci search was invented in 1960 by D.E. Ferguson. No normal human being would ever think of a search like this.]

For motivation in getting to Fibonacci search, let's review binary search. Also, to fit with the later search better, we'll assume our binary search starts with 1. So search an ordered array with elements A[1], ..., A[N] inclusive for y. We want an integer x, 0 < x < N+1 such that y == A[x] or else determine that no such x exists. At each stage of binary search, we have an interval [low, high]. (At the end we may have low == high.) We need to divide [low, high] into two parts: [low, mid], and [mid, high], and of course mid is midway between low and high (or as close as we can get). In case y == A[mid], we're done, and otherwise we know that y must be found using either [low, mid) or (mid, high], where a parenthesis means we are excluding the end value. Toward the end we may have mid == low or mid == high. In case we have low > high, we know the element isn't in the array.

With Fibonacci search, we start with the same ordered array A, except that N+1 must be a Fibonacci number, say, F[m+1]. We still want an integer x, 0 < x < N+1 = F[m+1]. Instead of the midpoint, we use the next Fibonacci number down: F[m].

Specific numbers will make this clearer: Take N = 54, so that N+1 = 55 = F[10]. We will be searching the sorted array: A[1], ..., A[54], inclusive. The array indexes are strictly between the two Fibonacci number: 0 < 55. Instead of the midpoint, this search uses the next Fibonacci number down from F[10] = 55, namely F[9] = 34. Instead of dividing the search interval in two, 50% on either side, we divide roughly by the golden ratio, roughly 62% to the left and 38% to the right. If y == A[34], then we've found it. Otherwise we have two smaller intervals to search: 0 to 34 and 34 to 55, not including the endpoints. If you have two successive Fibonacci numbers, it's easy to march backwards using subtraction, so that above, the next number back from 34 is 55 - 34 = 21. We would break up 0 to 34 with a 21 in the middle. The range from 34 to 55 is broken using the next Fibonacci number down: 34 - 21 = 13. The whole interval [34, 55] has length 21, and we go 13 past the start, to 34 + 13 = 47. Notice that this is not a Fibonacci number -- it's the lengths of all the intervals that are.

The table below shows possibilities for successive places to break up the range from 0 to 55. Every search of this array will either make its way into one of these ranges, and a few more steps beyond, or it will find the item along the way.

0                      <                       55 | -- one range of size 55
0          <           34          <           55 | -- two: 34, 21
0    <     21    <     34    <     47    <     55 | -- four: 21, 13, 13, 8
0  < 13 <  21 <  29 <  34 <  42 <  47  < 52 <  55 | -- eight: 13,8,8,5,8,5,5,3
0< 8<13<18<21<26<29<32<34<39<42<45<47<50<52<54<55 |
-- sixteen: 8,5,5,3,5,3,3,2,5,3,3,2,3,2,2,1

Here is sample data from a run of the program Fibonacci search program. In red above are the particular dividing integers that occur in the run below which made two more dividing steps.

Let y = A[x].  Want to find x.  N = 55.          
mid:34, p:21,q:13  |   0 < 34 < 55,  y > A[34], so 0  < x < 34
mid:21, p:13,q: 8  |   0 < 21 < 34,  y > A[34], so 21 < x < 34
mid:29, p: 5,q: 3  |  21 < 29 < 34,  y > A[29], so 29 < x < 34
mid:32, p: 2,q: 1  |  29 < 32 < 34,  y < A[32], so 29 < x < 32
mid:31, p: 1,q: 1  |  29 < 31 < 32,  y < A[31], so 29 < x < 31
mid:30, p: 1,q: 0  |  29 < 30 < 31,  y == A[30], x == 30
Found: 30

Here is the algorithm itself. Notice that this search does have a mid variable, and it has variables corresponding to low and high, namely the variables p and q, which are always Fibonacci numbers. However, unlike low and high, p and q are offsets from mid, and the search range is implicit rather than explicit.

// Fibonacci search, search A[1],A[2],...,A[N]
// Here N+1 must be a Fibonacci number, F[m+1]
int fibSearch(int y) { // y = A[x], 0 < x < F[m+1]
   int mid = F[m]; // F[m] is partway from 0 to F[m+1]
   int p   = F[m-1] = F[m] - F[m-1]
   int q   = F[m-2] = 2*F[m-1} - F[m]
   for (;;) {
      System.out.println("mid:" + mid + ", p:" + p + ",q:" + q);
      if (y == A[mid) return mid;
      else if (y < A[mid) {
         if (q == 0) return -(mid - 1);
         mid = mid - q;
         int temp = p;
         p = q;
         q = temp - q;
      }
      else if (y > A[mid]) {
         if (p == 1) return -mid;
         mid = mid + q;
         p = p - q;
         q = q - p;
      }
   }
}
Output with large numbers:
Using N = 3524577; i = 2178309;, searching for 1000000, got:
mid:2178309       p:1346269       q:832040
mid:1346269       p:832040        q:514229
mid:832040        p:514229        q:317811
mid:1149851       p:196418        q:121393
mid:1028458       p:121393        q:75025
mid:953433        p:75025         q:46368
mid:999801        p:28657         q:17711
mid:1017512       p:10946         q:6765
mid:1010747       p:6765          q:4181
mid:1006566       p:4181          q:2584
mid:1003982       p:2584          q:1597
mid:1002385       p:1597          q:987
mid:1001398       p:987           q:610
mid:1000788       p:610           q:377
mid:1000411       p:377           q:233
mid:1000178       p:233           q:144
mid:1000034       p:144           q:89
mid:999945        p:89            q:55
mid:1000000       p:34            q:21
Found: 1000000
Using N = 5702886; i = 3524578;, searching for 2000000, got:
mid:3524578       p:2178309       q:1346269
mid:2178309       p:1346269       q:832040
mid:1346269       p:832040        q:514229
mid:1860498       p:317811        q:196418
mid:2056916       p:121393        q:75025
mid:1981891       p:75025         q:46368
mid:2028259       p:28657         q:17711
mid:2010548       p:17711         q:10946
mid:1999602       p:10946         q:6765
mid:2006367       p:4181          q:2584
mid:2003783       p:2584          q:1597
mid:2002186       p:1597          q:987
mid:2001199       p:987           q:610
mid:2000589       p:610           q:377
mid:2000212       p:377           q:233
mid:1999979       p:233           q:144
mid:2000123       p:89            q:55
mid:2000068       p:55            q:34
mid:2000034       p:34            q:21
mid:2000013       p:21            q:13
mid:2000000       p:13            q:8
Found: 2000000