c 语言斐波那契搜索（Fibonacci Search）

给定一个大小为 n 的排序数组 arr[] 和要在其中搜索的元素 x。如果 x 存在于数组中，则返回 x 的索引，否则返回 -1。
例子：
输入： arr[] = {2, 3, 4, 10, 40}, x = 10
输出： 3
元素 x 出现在索引 3 处。

输入： arr[] = {2, 3, 4, 10, 40}, x = 11
输出： -1
元素 x 不存在。

        斐波那契搜索是一种基于比较的技术，它使用斐波那契数来搜索排序数组中的元素。
与二分查找的相似之处：
        1、适用于排序数组
        2、分而治之的算法。
        3、具有 Log n 时间复杂度。
与二分查找的区别：
        1、斐波那契搜索将给定数组分成不相等的部分
        2、二分查找使用除法运算符来划分范围。斐波那契搜索不使用 /，而是使用 + 和 -。在某些 CPU 上，除法运算符的成本可能很高。
        3、斐波那契搜索在后续步骤中检查相对较近的元素。因此，当输入数组很大，无法容纳 CPU 缓存甚至 RAM 时，斐波那契搜索可能会很有用。
背景：
        斐波那契数被递归地定义为 F(n) = F(n-1) + F(n-2)、F(0) = 0、F(1) = 1。前几个斐波那契数是 0、1、 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
观察：
下面的观察用于范围消除，因此用于 O(log(n)) 复杂度。
F(n - 2) ≈ (1/3)*F(n) 且
F(n - 1) ≈ (2/3)*F(n)。
算法：
设要查找的元素为x。
        这个想法是首先找到大于或等于给定数组长度的最小斐波那契数。令找到的斐波那契数为 fib（第 m 个斐波那契数）。我们使用第 (m-2) 个斐波那契数作为索引（如果它是有效索引）。设第(m-2)个斐波那契数为i，我们将arr[i]与x进行比较，如果x相同，则返回i。否则，如果 x 更大，则对 i 之后的子数组进行递归，否则对 i 之前的子数组进行递归。
下面是完整的算法
设 arr[0..n-1] 为输入数组，要搜索的元素为 x。
        1、找到大于或等于 n 的最小斐波那契数。令这个数字为 fibM [第 m 个斐波那契数]。令其前面的两个斐波那契数为 fibMm1 [(m-1) 个斐波那契数] 和 fibMm2 [(m-2) 个斐波那契数]。
        2、当数组有要检查的元素时：
                2.1、将 x 与 fibMm2 覆盖范围的最后一个元素进行比较
                2.2、如果x 匹配，则返回索引
                2.3、否则，如果x 小于该元素，则将三个斐波那契变量向下移动两个斐波那契，表示消除剩余数组的大约后三分之二。
                2.4、否则x 大于该元素，将三个斐波那契变量向下移动一位斐波那契。重置索引的偏移量。这些一起表明剩余阵列的大约前三分之一被消除。
        3、由于可能还剩下一个元素可供比较，因此检查 fibMm1 是否为 1。如果是，则将 x 与该剩余元素进行比较。如果匹配，则返回索引。

// C program for Fibonacci Search
#include <stdio.h>

// Utility function to find minimum of two elements
int min(int x, int y) { return (x <= y) ? x : y; }

/* Returns index of x if present, else returns -1 */
int fibMonaccianSearch(int arr[], int x, int n)
{
/* Initialize fibonacci numbers */
int fibMMm2 = 0; // (m-2)'th Fibonacci No.
int fibMMm1 = 1; // (m-1)'th Fibonacci No.
int fibM = fibMMm2 + fibMMm1; // m'th Fibonacci

/* fibM is going to store the smallest Fibonacci
Number greater than or equal to n */
while (fibM < n) {
fibMMm2 = fibMMm1;
fibMMm1 = fibM;
fibM = fibMMm2 + fibMMm1;
}

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

/* while there are elements to be inspected. Note that
we compare arr[fibMm2] with x. When fibM becomes 1,
fibMm2 becomes 0 */
while (fibM > 1) {
// Check if fibMm2 is a valid location
int i = min(offset + fibMMm2, n - 1);

/* If x is greater than the value at index fibMm2,
cut the subarray array from offset to i */
if (arr[i] < x) {
fibM = fibMMm1;
fibMMm1 = fibMMm2;
fibMMm2 = fibM - fibMMm1;
offset = i;
}

/* If x is greater than the value at index fibMm2,
cut the subarray after i+1 */
else if (arr[i] > x) {
fibM = fibMMm2;
fibMMm1 = fibMMm1 - fibMMm2;
fibMMm2 = fibM - fibMMm1;
}

/* element found. return index */
else
return i;
}

/* comparing the last element with x */
if (fibMMm1 && arr[offset + 1] == x)
return offset + 1;

/*element not found. return -1 */
return -1;
}

/* driver function */
int main(void)
{
int arr[]
= { 10, 22, 35, 40, 45, 50, 80, 82, 85, 90, 100,235};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 235;
int ind = fibMonaccianSearch(arr, x, n);
if(ind>=0)
printf("Found at index: %d",ind);
else
printf("%d isn't present in the array",x);
return 0;
}

输出
发现于索引：11
插图：
让我们通过下面的例子来理解算法：

示例假设：基于 1 的索引。目标元素 x 为 85。数组长度 n = 11。
        大于或等于 11 的最小斐波那契数为 13。根据我们的插图，fibMm2 = 5、fibMm1 = 8 和 fibM = 13。
        另一个实现细节是偏移变量（零初始化）。它标志着已被淘汰的范围，从前面开始。我们会不时更新。
        现在，由于偏移值是一个索引，并且包括它及其以下的所有索引都已被消除，因此只有向其添加一些内容才有意义。由于 fibMm2 标记了大约三分之一的数组，并且它标记的索引肯定是有效的，因此我们可以将 fibMm2 添加到 offset 并检查索引 i = min(offset + fibMm2, n) 处的元素。