1.写出斐波那契二分检索，即使用斐波那契数列二分有序序列，查找某给定元素，找到返回下标，找不到返回-1

斐波那契二分查找算法是一种利用斐波那契数列将数组分割成两部分进行查找的算法。其时间复杂度为O(logn)。

具体实现如下：

1. 定义一个斐波那契数列，长度不小于要查找的数组长度，例如：F[k] = F[k-1] + F[k-2]，其中 k >= 2，F[0] = 0，F[1] = 1。
2. 找到最小的斐波那契数列中大于等于要查找的数组长度的数列项，记为k。
3. 将原数组扩展到长度为F[k]。
4. 将扩展后的数组中多出的部分用原数组最后一个元素填充。
5. 定义三个指针：low、mid、high，分别指向要查找的区间的左、中、右三个位置。
6. 初始化时，low = 0，high = F[k]-1。
7. 如果要查找的元素小于mid位置上的元素，则在左半部分继续查找，将high指针移动到mid-1的位置，同时将mid指针的位置更新为low和high之间的斐波那契数列的前一个位置。
8. 如果要查找的元素大于mid位置上的元素，则在右半部分继续查找，将low指针移动到mid+1的位置，同时将mid指针的位置更新为low和high之间的斐波那契数列的后一个位置。
9. 如果要查找的元素等于mid位置上的元素，则返回mid。
10. 如果low大于high，则返回-1，表示未找到。

以下是斐波那契二分查找算法的示例代码：

int fibonacciSearch(int arr[], int n, int x)
{
    int fib2 = 0; // 前一个斐波那契数列的项
    int fib1 = 1; // 当前斐波那契数列的项
    int fib = fib1 + fib2; // 下一个斐波那契数列的项

    while (fib < n)
    {
        fib2 = fib1;
        fib1 = fib;
        fib = fib1 + fib2;
    }

    int offset = -1; // 记录数组扩展的偏移量
    while (fib > 1)
    {
        int i = min(offset + fib2, n - 1);
        if (arr[i] < x)
        {
            fib = fib1;
            fib1 = fib2;
            fib2 = fib - fib1;
            offset = i;
        }
        else if (arr[i] > x)
        {
            fib = fib2;
            fib1 = fib1 - fib2;
            fib2 = fib - fib1;
        }
        else
        {
            return i;
        }
    }

    if (fib1 && arr[offset + 1] == x)
    {
        return offset + 1;
    }

    return -1;
}