前言

“查找”学习提纲（三）——总结

系列文章

代码模板

查找方式的选择因素

  • 目的：静态查找或动态查找
  • 次序：无序或有序
  • 数据结构：顺序存储或链式存储；线性结构或非线性结构
  • 性能：低效或高效

线性查找

名称 适用 时间复杂度 空间复杂度
顺序查找 线性表 O(n) O(1)
折半查找 有序顺序表 O(logn) O(1)
插值查找 有序顺序表 O(logn) O(1)
斐波那契查找 有序顺序表 O(logn) O(m)
稠密索引查找 - - -
分块查找 线性表 O(logn)~O(n) O(m)
倒排索引查找 - - -

折半查找、插值查找和斐波那契查找

  • 过程相似，分隔值的选择策略不同，可能影响性能：折半查找为加法和除法运算，插值查找为加、减、乘和除法运算，斐波那契查找为加法和减法运算
  • 若数据规模大，关键字分布均匀，则性能：插值查找优于折半查找
  • 平均性能：斐波那契查找优于折半查找

树型查找

名称 适用 时间复杂度 空间复杂度
二叉排序树查找 动态表->二叉排序树 O(logn)~O(n) O(n)
平衡二叉排序树查找 动态表->平衡二叉排序树 O(logn) O(n)
红黑二叉排序树查找 动态表->红黑二叉排序树 O(logn) O(n)
B树查找 动态表->B树 O(logn) O(n)
B+树查找 动态表->B+树 O(logn) | O(mlogn) | O(logmlogn) O(n)

折半查找和二叉排序树查找

  • 过程相似

折半查找：

  • 适用有序顺序表
  • 二叉判定树唯一
  • 插入和删除的时间复杂度：O(n)。n为数据规模

二叉排序树查找：

  • 适用动态表
  • 二叉排序树不唯一（关键字相同，插入顺序不同）
  • 插入和删除的时间复杂度：O(logn)。n为数据规模（平均情况）

二叉排序树查找、平衡二叉排序树查找和红黑二叉排序树查找

  • 一般性能：平衡二叉排序树查找和红黑二叉排序树查找优于二叉排序树查找
  • 若插入和删除操作相对少，查找操作相对多，适用平衡二叉排序树查找
  • 若插入和删除操作相对多，查找操作相对少，适用红黑二叉排序树查找

散列查找

名称 适用 时间复杂度 空间复杂度
散列查找 查找性能要求高，记录关系无要求 O(1) O(m)

总表

名称 适用 时间复杂度 空间复杂度
顺序查找 线性表 O(n) O(1)
折半查找 有序顺序表 O(logn) O(1)
插值查找 有序顺序表 O(logn) O(1)
斐波那契查找 有序顺序表 O(logn) O(m)
稠密索引查找 - - -
分块查找 线性表 O(logn)~O(n) O(m)
倒排索引查找 - - -
二叉排序树查找 动态表->二叉排序树 O(logn)~O(n) O(n)
平衡二叉排序树查找 动态表->平衡二叉排序树 O(logn) O(n)
红黑二叉排序树查找 动态表->红黑二叉排序树 O(logn) O(n)
B树查找 动态表->B树 O(logn) O(n)
B+树查找 动态表->B+树 O(logn) | O(mlogn) | O(logmlogn) O(n)
散列查找 查找性能要求高，记录关系无要求 O(1) O(m)

作者的话

  • 感谢参考资料的作者/博主
  • 作者：夜悊
  • 版权所有，转载请注明出处，谢谢~
  • 如果文章对你有帮助，请点个赞或加个粉丝吧，你的支持就是作者的动力~
  • 文章在描述时有疑惑的地方，请留言，定会一一耐心讨论、解答
  • 文章在认识上有错误的地方, 敬请批评指正
  • 望读者们都能有所收获