6

#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

using namespace std;

int fibonaccianSearch(int arr[], int n, int x){
    /* Инициализация чисел Фибоначчи */
    int fibMMm2 = 0; // (m-2)-е число Фибоначчи
    int fibMMm1 = 1; // (m-1)-е число Фибоначчи
    int fibM = fibMMm2 + fibMMm1; // m-е число Фибоначчи
    /* Находим диапазон чисел Фибоначчи, в котором находится
    число n */
    while (fibM < n){
        fibMMm2 = fibMMm1;
        fibMMm1 = fibM;
        fibM = fibMMm2 + fibMMm1;
    }
    // отмечаем выбранный диапазон
    int offset = -1;
    while (fibM > 1){
        // Проверяем, является ли fibMm2 допустимым местоположением
        int i = min(offset+fibMMm2, n-1);
        /* Если X больше, чем значение индекса fibMm2,
        исключить подмассив массива от offset to i */
        if (arr[i] < x){
            fibM = fibMMm1;
            fibMMm1 = fibMMm2;
            fibMMm2 = fibM - fibMMm1;
            offset = i;
        }
        /* Если X меньше, чем значение индекса fibMm2,
        исключить подмассив массива после i+1 */
        else if (arr[i] > x){
            fibM = fibMMm2;
            fibMMm1 = fibMMm1 - fibMMm2;
            fibMMm2 = fibM - fibMMm1;
        }
        /* Элемент найден. Возвращаем индекс */
        else return i;
    }
    /* сравнение последнего элемента с x */
    if(fibMMm1 && arr[offset+1]==x)return offset+1;
    /*Элемент не найден. Возвращаем -1 */
    return -1;
}

int main() {
    srand(time(NULL));
    int n;
    cin >> n;
    int *a = new int[n];
    for (int i = 0; i < n; i++) a[i] = rand() % 50;
    sort(a, a + n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    int key;
    cin >> key;
    cout << "index " << fibonaccianSearch(a, n, key) << endl;
    delete [] a;
    return 0;
}