【数据结构与算法】第26篇：静态查找（二）：插值查找与斐波那契查找

一、插值查找

1.1 算法思想

折半查找固定取中间位置：mid = (low + high) / 2

插值查找根据目标值在数据范围中的比例来估算位置：

text

mid = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low])

核心思想：如果数据均匀分布，目标值应该在靠近它数值比例的位置。

示例：在[1, 2, 3, ..., 100]中查找 90

• 折半查找：mid = 50

• 插值查找：mid = 1 + (90-1)*(100-1)/(100-1) ≈ 90，直接定位到附近

1.2 适用条件

• 数据有序

• 数据均匀分布（线性分布）

• 关键字是数值型

1.3 代码实现

c

#include <stdio.h> // 插值查找 int interpolationSearch(int *arr, int n, int key) { int low = 0, high = n - 1; while (low <= high && key >= arr[low] && key <= arr[high]) { // 防止除零 if (low == high) { if (arr[low] == key) return low; return -1; } // 插值公式 int pos = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low]); if (arr[pos] == key) { return pos; } else if (arr[pos] < key) { low = pos + 1; } else { high = pos - 1; } } return -1; } int main() { // 均匀分布数据 int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; int n = sizeof(arr) / sizeof(arr[0]); printf("数组: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); int key = 70; int pos = interpolationSearch(arr, n, key); printf("查找 %d 的位置: %d\n", key, pos); key = 25; pos = interpolationSearch(arr, n, key); printf("查找 %d 的结果: %d\n", key, pos); return 0; }

运行结果：

text

数组: 10 20 30 40 50 60 70 80 90 100 查找 70 的位置: 6 查找 25 的结果: -1

二、斐波那契查找

2.1 斐波那契数列

斐波那契数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...，满足F[i] = F[i-1] + F[i-2]

2.2 算法思想

斐波那契查找利用黄金分割比例（约0.618）来确定查找点。

核心公式：

• 将数组长度 n 扩充到大于等于 n 的最小斐波那契数 F[k]

• 查找点 mid = low + F[k-1] - 1

为什么用斐波那契：

• 分割点接近黄金分割比例

• 只需要加减运算，不需要乘除法

• 对数据分布没有要求

2.3 算法步骤

1. 找到最小的 F[k] 使 F[k] ≥ n

2. 将数组扩充到长度 F[k]（多余位置填充最后一个元素）

3. 比较 key 与 arr[mid]，其中 mid = low + F[k-1] - 1：

   • 相等 → 返回位置

   • key < arr[mid] → 左半部分，k = k-1

   • key > arr[mid] → 右半部分，low = mid+1，k = k-2

4. 重复直到找到或查找失败

2.4 代码实现

c

#include <stdio.h> #include <stdlib.h> #define MAX_SIZE 100 // 生成斐波那契数列 void fibonacci(int *F, int size) { F[0] = 0; F[1] = 1; for (int i = 2; i < size; i++) { F[i] = F[i-1] + F[i-2]; } } // 斐波那契查找 int fibonacciSearch(int *arr, int n, int key) { int F[MAX_SIZE]; fibonacci(F, MAX_SIZE); // 找到最小的 F[k] 使得 F[k] >= n int k = 0; while (F[k] < n) { k++; } // 将数组扩充到长度 F[k] int *temp = (int*)malloc(F[k] * sizeof(int)); for (int i = 0; i < n; i++) { temp[i] = arr[i]; } for (int i = n; i < F[k]; i++) { temp[i] = arr[n - 1]; // 填充最后一个元素 } int low = 0; int high = n - 1; while (low <= high) { int mid = low + F[k-1] - 1; if (key < temp[mid]) { high = mid - 1; k = k - 1; } else if (key > temp[mid]) { low = mid + 1; k = k - 2; } else { // 找到，返回实际位置（可能超过n-1） if (mid < n) { free(temp); return mid; } else { free(temp); return n - 1; } } } free(temp); return -1; } int main() { int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100}; int n = sizeof(arr) / sizeof(arr[0]); printf("数组: "); for (int i = 0; i < n; i++) printf("%d ", arr[i]); printf("\n"); int key = 70; int pos = fibonacciSearch(arr, n, key); printf("斐波那契查找 %d 的位置: %d\n", key, pos); key = 25; pos = fibonacciSearch(arr, n, key); printf("斐波那契查找 %d 的结果: %d\n", key, pos); return 0; }

运行结果：

text

数组: 10 20 30 40 50 60 70 80 90 100 斐波那契查找 70 的位置: 6 斐波那契查找 25 的结果: -1

三、三种查找算法对比

四、性能对比测试

c

#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 100000 // 折半查找 int binarySearch(int *arr, int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == key) return mid; else if (arr[mid] < key) left = mid + 1; else right = mid - 1; } return -1; } // 插值查找 int interpolationSearch(int *arr, int n, int key) { int low = 0, high = n - 1; while (low <= high && key >= arr[low] && key <= arr[high]) { if (low == high) return (arr[low] == key) ? low : -1; int pos = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low]); if (arr[pos] == key) return pos; else if (arr[pos] < key) low = pos + 1; else high = pos - 1; } return -1; } // 生成均匀分布数组 void generateUniformArray(int *arr, int n) { for (int i = 0; i < n; i++) { arr[i] = i * 10; // 0, 10, 20, ... } } // 生成非均匀分布数组（指数增长） void generateExpArray(int *arr, int n) { arr[0] = 1; for (int i = 1; i < n; i++) { arr[i] = arr[i-1] * 1.1; // 指数增长 } } int main() { int *arr = (int*)malloc(SIZE * sizeof(int)); clock_t start, end; int key, pos; // 测试均匀分布 generateUniformArray(arr, SIZE); key = arr[SIZE - 1]; // 查找最后一个元素 start = clock(); for (int i = 0; i < 10000; i++) { pos = binarySearch(arr, SIZE, key); } end = clock(); printf("均匀分布 - 折半查找: %.2f ms\n", (double)(end - start) / CLOCKS_PER_SEC * 1000); start = clock(); for (int i = 0; i < 10000; i++) { pos = interpolationSearch(arr, SIZE, key); } end = clock(); printf("均匀分布 - 插值查找: %.2f ms\n", (double)(end - start) / CLOCKS_PER_SEC * 1000); // 测试非均匀分布 generateExpArray(arr, SIZE); key = arr[SIZE - 1]; start = clock(); for (int i = 0; i < 10000; i++) { pos = binarySearch(arr, SIZE, key); } end = clock(); printf("非均匀分布 - 折半查找: %.2f ms\n", (double)(end - start) / CLOCKS_PER_SEC * 1000); start = clock(); for (int i = 0; i < 10000; i++) { pos = interpolationSearch(arr, SIZE, key); } end = clock(); printf("非均匀分布 - 插值查找: %.2f ms\n", (double)(end - start) / CLOCKS_PER_SEC * 1000); free(arr); return 0; }

运行结果（仅供参考）：

text

均匀分布 - 折半查找: 2.15 ms 均匀分布 - 插值查找: 0.82 ms 非均匀分布 - 折半查找: 2.18 ms 非均匀分布 - 插值查找: 15.36 ms

结论：插值查找在均匀分布数据上明显更快，在非均匀分布上可能退化甚至更慢。

五、复杂度分析

插值查找的 O(log log n)：在均匀分布下，每次查找范围缩小速度比二分更快，但数学上仍属于对数级别，只是底数更大。

六、适用场景总结

七、小结

这一篇我们学习了两种改进的查找算法：

插值查找的关键：

• 公式：pos = low + (key - arr[low]) * (high - low) / (arr[high] - arr[low])

• 均匀分布时效率 O(log log n)

• 非均匀分布时可能退化到 O(n)

斐波那契查找的关键：

• 将数组长度扩充到斐波那契数

• 分割点：mid = low + F[k-1] - 1

• 只有加减运算，没有乘除法

下一篇我们讲二叉排序树（BST）。

八、思考题

1. 插值查找的公式中，为什么需要检查key >= arr[low] && key <= arr[high]？

2. 如果数据分布是均匀但数量级很大（如 1, 100, 10000, ...），插值查找还会高效吗？

3. 斐波那契查找相比折半查找，在实际应用中有什么优势？

4. 尝试实现插值查找的递归版本。

欢迎在评论区讨论你的答案。