bf算法，用c语言来实现

BF（Binary Fibonacci）算法，也称为二进制指数搜索法，是一种用于查找目标值在有序数组中位置的搜索算法。它的工作原理是利用斐波那契数列的思想，通过将搜索范围逐步缩小到斐波那契数级别的方式，减少了搜索次数。

以下是使用C语言实现BF算法的基本步骤：

#include <stdio.h>

// 斐波那契函数
unsigned long long fibonacci(int n) {
    if (n <= 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

// BF搜索函数
int binary_fib_search(int arr[], unsigned long long target, int low, int high) {
    while (low <= high) {
        // 计算当前的搜索区间大小，等于最近的斐波那契数
        int fib = fibonacci(min(high - low + 1, 3)); // 由于斐波那契数列增长快，我们限制查找长度不超过3

        // 将搜索区间分为两部分
        int mid = low + fib / 2;
        if (arr[mid] == target)
            return mid; // 找到了目标值，直接返回索引
        else if (arr[mid] < target)
            low = mid + fib; // 如果目标值大于中间值，移动到右半部分
        else
            high = mid - fib; // 否则，移动到左半部分
    }
    return -1; // 没有找到目标值，返回-1表示不存在
}

int main() {
    int arr[] = {1, 3, 5, 8, 13, 21, 34}; // 示例数组
    int n = sizeof(arr) / sizeof(arr[0]);
    unsigned long long target = 13;

    int result_index = binary_fib_search(arr, target, 0, n - 1);
    if (result_index != -1)
        printf("Target %llu found at index %d\n", target, result_index);
    else
        printf("Target not found in the array.\n");

    return 0;
}