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

一、插值查找1.1 算法思想折半查找固定取中间位置mid (low high) / 2插值查找根据目标值在数据范围中的比例来估算位置textmid 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 算法步骤找到最小的 F[k] 使 F[k] ≥ n将数组扩充到长度 F[k]多余位置填充最后一个元素比较 key 与 arr[mid]其中 mid low F[k-1] - 1相等 → 返回位置key arr[mid] → 左半部分k k-1key arr[mid] → 右半部分low mid1k k-2重复直到找到或查找失败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三、三种查找算法对比算法分割点时间复杂度适用场景优缺点折半查找mid (lowhigh)/2O(log n)通用有序表简单稳定插值查找按比例计算O(log log n) 平均均匀分布分布不均匀时退化斐波那契查找mid lowF[k-1]-1O(log n)通用有序表只有加减运算四、性能对比测试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(1)O(log n)O(log n)插值查找O(1)O(log log n)O(n)斐波那契查找O(1)O(log n)O(log n)插值查找的 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。八、思考题插值查找的公式中为什么需要检查key arr[low] key arr[high]如果数据分布是均匀但数量级很大如 1, 100, 10000, ...插值查找还会高效吗斐波那契查找相比折半查找在实际应用中有什么优势尝试实现插值查找的递归版本。欢迎在评论区讨论你的答案。