fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. int square(int num) {
  7.     return num * num;
  8. }
  9.  
  10. template<typename T>
  11. void print_v(vector<T> v)
  12. {
  13.     cout << "v out:" << endl;
  14.     for(auto item = v.begin(); item != v.end(); ++item)
  15.     {
  16.         cout << *item << " ";
  17.     }
  18.     cout << endl;
  19. }
  20.  
  21. int SequentialSearch(vector<int>& v, int key)
  22. {
  23. 	for(int i=0; i< v.size();i++)
  24. 	{
  25. 		if (v[i] == key)
  26. 		{
  27. 			return i;
  28. 		}
  29. 	}
  30.     return -1;
  31. }
  32.  
  33. int BinarySearch(vector<int>& v, int key)
  34. {
  35.     int low = 0;
  36.     int high = v.size();
  37.     while(low < high)
  38.     {
  39.         //int mid = (high - low)/2;
  40.         int mid = low + (high - low)*(key -v[low])/(v[high] - v[low]);
  41.         if(key == v[mid])
  42.         {
  43.             return mid;
  44.  
  45.         }
  46.         else if(key < v[mid])
  47.         {
  48.             high = mid-1;
  49.         }
  50.         else
  51.         {
  52.             low = mid+1;
  53.         }
  54.     }
  55.     return -1;
  56. }
  57.  
  58. void GenFibonacci(vector<int>& fv, int max)
  59. {
  60.     if (fv.size()<2)
  61.     {
  62.         fv.push_back(0);
  63.         fv.push_back(1);
  64.     }
  65.     auto v_size = fv.size();
  66.     if (fv[v_size-1] >= max)
  67.         return;
  68.     fv.push_back(fv[v_size -2] + fv[v_size - 1]);
  69.     GenFibonacci(fv, max);
  70. }
  71.  
  72.  
  73. int FibonacciSearch(vector<int>& sv, int key)
  74. {
  75.     int n = sv.size();
  76.     vector<int> fv;
  77.     GenFibonacci(fv, sv.size());
  78.     print_v<int>(fv);
  79.     int k = fv.size()-1;
  80.     while(sv.size() < fv[k-1]-1)
  81.     {
  82.         sv.push_back(*sv.rbegin());
  83.     }
  84.     print_v<int>(sv);
  85.     int low = 0;
  86.     int high = sv.size();
  87.     while(low <= high)
  88.     {
  89.         int mid = low + fv[k-1]-1;
  90.         cout << mid << " "  << sv[mid] << " " << low << " "<< high << endl;
  91.         if(key < sv[mid])
  92.         {
  93.             high = mid - 1;
  94.             k = k - 1;
  95.         }
  96.         else if(key > sv[mid])
  97.         {
  98.             low = mid + 1;
  99.             k = k - 2;
  100.         }
  101.         else
  102.         {
  103.             if (mid < n)
  104.                 return mid;
  105.             else
  106.                 return n;
  107.         }
  108.     }
  109.     return -1;
  110. }
  111.  
  112.  
  113. int main() {
  114. 	vector<int> v1 = {1,2,4,5,7,8,9,10};
  115. 	auto index = FibonacciSearch(v1, 11);
  116. 	cout << "index: " << index << endl;
  117. 	return 0;
  118. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
v out:
0 1 1 2 3 5 8 
v out:
1 2 4 5 7 8 9 10 
4 7 0 8
6 9 5 8
7 10 7 8
7 10 8 8
7 10 8 8
7 10 8 8
7 10 8 8
7 10 8 8
7 10 8 8
11083 0 8 8
index: -1
https://ideone.com/fBekPN
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!