fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. // The function return index of x if present, else return -1
  6. int fibonacciSearch(vector<int> arr, int x)
  7. {
  8.     int fib2 = 0, fib1 = 1, fib = 1, n =  arr.size();
  9.  
  10.     while (fib < n) // Find the largest fibonacci number less than or equal to array size
  11.     {
  12.         fib2 = fib1;
  13.         fib1 = fib;
  14.         fib = fib1 + fib2;
  15.     }
  16.  
  17.     int offset = -1; // Marks the eliminated range from front
  18.  
  19.     while (fib > 1)
  20.     {
  21.         int index = min(offset + fib2, n - 1);
  22.  
  23.         // If x is greater than the value at index fib2, cut the subarray from offset to index
  24.         if (arr[index] < x) // Skip the left
  25.         {
  26.             fib = fib1;
  27.             fib1 = fib2;
  28.             fib2 = fib - fib1;
  29.             offset = index;
  30.         }
  31.  
  32.         // If x is less
  33.         else if (arr[index] > x) // Skip the right
  34.         {
  35.             fib = fib2;
  36.             fib1 = fib1 - fib2;
  37.             fib2 = fib - fib1;
  38.         }
  39.  
  40.         else return index; // Found the element
  41.     }
  42.  
  43.     if (fib1 > 0 && arr[offset + 1] == x) return offset + 1; // Compare the last element with x
  44.  
  45.     return -1; // Not found
  46. }
  47.  
  48. int main()
  49. {
  50.     vector<int> arr{0, 4, 5, 7, 9, 12, 13};
  51.  
  52.     cout << fibonacciSearch(arr, 11);
  53.  
  54.     return 0;
  55. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/fzDM4J
language:
C++14 (gcc 8.3)
created:
12 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!