一、基本查找算法对比算法时间复杂度空间复杂度适用条件平均查找长度（ASL）公式特点顺序查找O(n)O(1)无序/有序线性表成功：(n+1)/2失败：n+1可用哨兵优化折半查找O(log n)O(1)有序顺序表成功：向下取整[log₂(n)] + 1需随机访问，链表不可用分块查找O(√n)（理想块大小）O(1)块间有序+块内无序索引顺序+块内顺序：(b+1)/2+(s+1)/2动态索引效率高顺序查找：最好：表头开始，O(1)最坏：表尾开始，O(n)平均：(n+1) / 2，所以是O(n)折半查找：最大比较次数（二叉搜索树）=向下取整[log₂(n)] + 1（例如：一个长度16的顺序表元素按关键字有序排列，找一个表中不存在的元素则key之间比较次数最多是：5次）。最少比较次数：1次。🚩不适用场景：链表（因为无法随机访问）。例：有序链表，无序数组，有序静态链表，无序静态链表。折半查找判定树：观察其左倾，右倾，一棵树在查找时会固定要么左要么右，不会找到一半改变方向。二叉搜索树保证有序分块查找：索引表必须有序二、分块查找➡平均查找长度ASL = 索引查找 + 块内查找1. 性能公式对比假设长n的表，分成b块，每块里面有s条索引查找块内查找ASL公式示例（n=100, b=10, s=10）顺序查找顺序查找(b+1)/2 + (s+1)/25.5 + 5.5 = 11折半查找顺序查找向下取整[log₂(b)] + 1 + (s+1)/24 + 5.5 = 9.5最佳块大小-s=√n 时 ASL最小≈√n√100=102. 块划分原则块间有序：第i块最大关键字 第i+1块最小关键字块内无序：块内无需排序，节省维护成本索引表结构：存储每块的最大关键字和起始地址3. ASL计算误区失败查找长度 ≠ 成功查找长度分块查找：需分开计算索引和块内查找三、🚩折半查找1. 判定树性质