フィボナッチ数の助けを借りて分割統治法を使用してソートされたシーケンスを検索するC++プログラム

このC++プログラムでは、フィボナッチ数を使用して分割統治法を実装します。フィボナッチ数を使用して、データ配列の中央を計算し、データ項目を検索します。このアプローチの時間計算量はO（log（n））です。

アルゴリズム

Begin
   Assign the data to the array in a sorted manner.
   Take input of the element to be searched.
   Call FibonacciSearch() function.
   Calculate the mid value using ‘start+fib[index-2]’ expression.
   If the chosen item is equal to the value at mid index, print result and return to main.
   If it is lesser than the value at mid index, proceed with the left sub-array.
   If it is more than the value at mid index, proceed with the right sub-array.
   If the calculated mid value is equal to either start or end then the item is not found in the array.
End

サンプルコード

#include<iostream>
using namespace std;
void FibonacciSearch(int *a, int start, int end, int *fib, int index, int item) {
   int i, mid;
   mid = start+fib[index-2];
   if(item == a[mid]) {
      cout<<"\n item found at "<<mid<<" index.";
      return;
   } else if(item == a[start]) {
      cout<<"\n item found at "<<start<<" index.";
      return;
   } else if(item == a[end]) {
      cout<<"\n item found at "<<end<<" index.";
      return;
   } else if(mid == start || mid == end) {
      cout<<"\nElement not found";
      return;
   } else if(item > a[mid])
         FibonacciSearch(a, mid, end, fib, index-1, item);
      else
         FibonacciSearch(a, start, mid, fib, index-2, item);
   }
   main() {
      int n, i, fib[20], a[10]={3, 7, 55, 86, 7, 15, 26, 30, 46, 95};
      char ch;
      fib[0] = 0;
      fib[1] = 1;
      i = 1;
      while(fib[i] < 10) {
         i++;
         fib[i] = fib[i-1] + fib[i-2];
      }
      up:
         cout<<"\nEnter the Element to be searched: ";
         cin>>n;
         FibonacciSearch(a, 0, 9, fib, i, n);
         cout<<"\n\n\tDo you want to search more...enter choice(y/n)?";
         cin>>ch;
         if(ch == 'y' || ch == 'Y')
            goto up;
         return 0;
   }
}

出力

Enter the Element to be searched: 26
item found at 6 index.
Do you want to search more...enter choice(y/n)?y
Enter the Element to be searched: 45
item not found
Do you want to search more...enter choice(y/n)?n