fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int fibMonaccianSearch(vector<int> arr, int x, int n)
  5. {
  6.  
  7.     int fibMMm2 = 0; 
  8.     int fibMMm1 = 1;
  9.     int fibM = fibMMm2 + fibMMm1;
  10.     while (fibM < n) {
  11.         fibMMm2 = fibMMm1;
  12.         fibMMm1 = fibM;
  13.         fibM = fibMMm2 + fibMMm1;
  14.     }
  15.     int offset = -1;
  16.  
  17.     while (fibM > 1) {
  18.         int i = min(offset + fibMMm2, n - 1);
  19.  
  20.         if (arr[i] < x) {
  21.             fibM = fibMMm1;
  22.             fibMMm1 = fibMMm2;
  23.             fibMMm2 = fibM - fibMMm1;
  24.             offset = i;
  25.         }
  26.  
  27.         else if (arr[i] > x) {
  28.             fibM = fibMMm2;
  29.             fibMMm1 = fibMMm1 - fibMMm2;
  30.             fibMMm2 = fibM - fibMMm1;
  31.         }
  32.  
  33.  
  34.         else
  35.             return i;
  36.     }
  37.     if (fibMMm1 && arr[offset + 1] == x)
  38.         return offset + 1;
  39.  
  40.     return -1;
  41. }
  42. int main()
  43. {
  44.     int n; cin >> n;
  45.     vector<int> a(n);
  46.     for(int i=0; i<n; i++){
  47.         cin >> a[i];
  48.     }
  49.     cout << fibMonaccianSearch(a, 4,n);
  50. }
  51.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
5
1 2 3 4 5
stdout
copy 
3
https://ideone.com/YksuCE
language:
C++14 (gcc 8.3)
created:
13 days 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!