本文共 1508 字，大约阅读时间需要 5 分钟。
在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文将简单介绍常见的七种查找算法，其中二分查找、插值查找及斐波那契查找都属于插值查找的一种优化。插值查找和斐波那契查找是在二分查找的基础上提出的优化算法。
查找是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
查找算法可以分为静态查找和动态查找，或者无序查找和有序查找。动态查找表指的是查找表中有删除和插入操作的表。无序查找适用于被查找数列有序无序均可，而有序查找则要求被查找数列必须为有序数列。
平均查找长度（ASL）是指在查找成功时，与指定key比较的关键字个数的期望值。对于含有n个数据元素的查找表，ASL=Pi*Ci的和，其中Pi是查找表中第i个数据元素的概率，Ci是找到第i个数据元素时已经比较过的次数。
顺序查找也称为线形查找，是无序查找算法的一种。从数据结构线形表的一端开始，顺序扫描，依次将扫描到的结点关键字与给定值k比较，若相等则查找成功；若扫描结束仍未找到，则查找失败。
查找成功时的平均查找长度为(n+1)/2，时间复杂度为O(n)。
二分查找是一种有序查找算法，通过将有序表分成两部分，逐步缩小查找范围。具体步骤是：用给定值k与中间结点的关键字比较，若相等则查找成功；若不相等，则根据比较结果确定下一步查找哪个子表，直到查找到或查找结束。
最坏情况下，比较次数为log2(n+1)，期望时间复杂度为O(log2n)。
插值查找是在二分查找的基础上提出的优化算法。通过计算查找点的比例参数，使其更接近目标值，从而减少比较次数。插值查找适用于表长较大且关键字分布较均匀的情况。
查找成功或失败的时间复杂度均为O(log2(log2n))。
斐波那契查找是一种改进的二分查找算法，利用斐波那契数列的黄金比例特性来确定查找点。查找过程分为三种情况：等于、大于和小于，分别调整查找范围。
时间复杂度为O(log2n)，期望复杂度也为O(log2n)。
树表查找以二叉查找树为基础，通过递归比较每个节点的值来确定查找方向。二叉查找树的性质是左子树值小于右子树值，中序遍历可得到有序数列。
插入和查找的时间复杂度均为O(logn)，但最坏情况下仍为O(n)。
分块查找将数据分为若干块，块与块之间按顺序排列。查找时首先在块间进行二分查找，确定目标块，再在块内进行顺序查找。
时间复杂度为O((logm + logn) + n/m)，其中m为块数，n为数据元素个数。
哈希查找通过将记录的关键字映射到数组索引上，直接访问即可找到目标记录。常见的冲突处理方法有拉链法和线性探测法。
无冲突情况下，查找时间复杂度为O(1)，空间复杂度为O(n)。
通过哈希表或数组的排序遍历找到重复的数字，时间复杂度为O(n)。
使用归并排序统计逆序对个数，时间复杂度为O(n logn)。
利用归并排序或优先队列获取最小的K个数，时间复杂度为O(n logn)。
使用两堆（大顶堆和小顶堆）来维护数据流中的中位数，时间复杂度为O(n)。
转载地址：http://bmhfk.baihongyu.com/