피보나치 수의 도움으로 나눗셈을 사용하여 정렬된 시퀀스를 검색하는 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