#include <iostream>
#include <vector>
using namespace std;

// The function return index of x if present, else return -1
int fibonacciSearch(vector<int> arr, int x)
{
    int fib2 = 0, fib1 = 1, fib = 1, n =  arr.size();

    while (fib < n) // Find the largest fibonacci number less than or equal to array size
    {
        fib2 = fib1;
        fib1 = fib;
        fib = fib1 + fib2;
    }

    int offset = -1; // Marks the eliminated range from front

    while (fib > 1)
    {
        int index = min(offset + fib2, n - 1);

        // If x is greater than the value at index fib2, cut the subarray from offset to index
        if (arr[index] < x) // Skip the left
        {
            fib = fib1;
            fib1 = fib2;
            fib2 = fib - fib1;
            offset = index;
        }

        // If x is less
        else if (arr[index] > x) // Skip the right
        {
            fib = fib2;
            fib1 = fib1 - fib2;
            fib2 = fib - fib1;
        }

        else return index; // Found the element
    }
    
    if (fib1 > 0 && arr[offset + 1] == x) return offset + 1; // Compare the last element with x

    return -1; // Not found
}

int main()
{
    vector<int> arr{0, 4, 5, 7, 9, 12, 13};

    cout << fibonacciSearch(arr, 11);

    return 0;
}