zum Inhalt springen

Fibonacci Suche

C++ Quellcode

#include<iostream>
using namespace std;


// *****************************
// Fibunacci Suche
// *****************************
int fibsearch(int *A, int m, int k)
{
    int pos = -1;
    int f1 = 0, f2 = 1, f3 = 1;
    while (f3 - 1 < m)
    {
          f1 = f2;
          f2 = f3;
          f3 = f1 + f2;
    }
    int i = f2, t;

      do
    {
        if (k>A[i])
        {
                   // Durchsuche den oberen Bereich
                   if (f1 == 0) pos = 0; // nicht vorhanden
                   else
                  {
                       i  += f1;
                       t    = f1;
                      f1   = f2 - f1;
                      f2   = t;
                  }
            }
            else if (k<A[i])
        {
                   // Dursuche den unteren Bereich
                   if(f2==1) pos = 0; // nicht vorhanden
                   else
                  {
                       i  -= f1;
                      f2 -= f1;
                      f1 -= f2;
                  }
            }
            else pos = i; // gefunden
      } while (pos < 0);
      return pos;
}


// *****************************
// los geht's
// *****************************
int main()
{
    int A[]={1,2,3,4,5,6,7,8,9};
    int n=sizeof(A)/sizeof(int);
    int pos = fibsearch(A,n-1,7);
    cout << pos << ": " << A[pos] << endl;
}