分析&回答
| 平均时间复杂度 | 最差查找时间 | 查找前提 | 前提时间复杂度 | 插入新值时间 | |
|---|---|---|---|---|---|
| 顺序查找 | O(n) | O(n) | 无序或有序队列 | 无 | O(1) |
| 二分查找 | O(㏒n) | O(㏒n) | 排序（有序数组） | O(n㏒n) | O(n) |
| 插值查找 | O(㏒(㏒n)) | O(㏒(㏒n)) | 排序 | O(n㏒n) | O(n) |
| 斐波那契查找 | O(㏒n) | O(㏒n) | 排序+斐波那契数列 | O(n㏒n) | O(n) |
| 二叉树查找 | O(㏒n) | O(n) | 创建二叉树 | O(n㏒n) | O(㏒n) |
| 2-3树(k在2-3之间） | O(logk n) | O(logk n) | 创建2-3树 | O(nlogk n) | O(logk n) |
| 红黑树 | O(㏒n) | O(2㏒n) | 创建红黑树 | O(n㏒n) | O(㏒n) |
| B树和B+树（m为阶数） | O(log m/2 n/2) | O(log m/2 n/2) | 创建B树和B+树 | O(nlog m n) | O(log m n) |
| 区块查找(b为块数） | O(㏒b +n/b) | O(㏒b +n/b) | 创建区块 | O(n㏒b) | O(㏒b) |
| 哈希查找(k为一格的链表长度） | O(1) | O(k) | 创建哈希表 | O(n) | O(1) |
反思&扩展
特别关注二分查找、二叉树查找、红黑树
通常把查找过程中对关键字的平均比较次数，也叫平均查找长度（ASL）作为衡量一个查找算法效率优劣的标准：
ASL=求和(p[i]*c[i])，(i=1~n)。P[i]找到第i个记录的概率，c[i]找到第i个记录进行比较的次数
顺序查找的思想：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k比较，若当前扫描的关键字与k相等，则查找成功，
若扫描结束后，任未发现关键字等于k的记录，则查找失败。
ASL1查找成功（求和）i/n,i=1~n.
ASL2查找失败n
喵呜面试助手： 一站式解决面试问题，你可以搜索微信小程序 [喵呜面试助手] 或关注 [喵呜刷题] -> 面试助手 免费刷题。如有好的面试知识或技巧期待您的共享！
