有序表查找分析：顺序与折半查找的平均长度计算

"第9章查找.pdf" 在计算机科学中，查找是数据结构和算法领域中的一个核心概念。本章主要探讨了两种常见的查找方法：顺序查找和折半查找，以及如何计算这两种查找方法的平均查找长度（ASL）。 顺序查找是一种简单直观的方法，它从数据集的第一个元素开始，逐个比较目标值直到找到或遍历完整个列表。在给定的有序表（do, for, if, repeat, while）中，每个元素的查找概率不同。例如，查找'do'的概率是0.2，而查找'while'的概率是0.01。如果查找成功，顺序查找的平均查找长度等于查找每个元素的概率乘以其对应的索引加权和；如果查找不成功，则为查找每个不存在元素的概率乘以其对应的层次加权和。对于这个特定的有序表，顺序查找成功的ASL是0.97，不成功的ASL是1.07。 折半查找，也称为二分查找，适用于有序数组。它通过每次将搜索范围减半来提高效率。在给定的有序表上，折半查找的判定树呈现出二叉树结构。成功的ASL是所有内部节点（表示查找成功的情况）的层次加权和，而不成功的ASL则是所有外部节点（查找不成功的情况）的层次加权和减1。对于这个例子，折半查找成功的ASL是1.04，不成功的ASL是1.3。 接下来，我们考虑另一个有序表A[0..10]，在等概率的情况下，折半查找的ASL计算方式类似。成功查找的ASL是所有内部节点层次的平均值，不成功查找则为外部节点层次的平均值减1。对于有序表（12, 18, 24, 35, 47, 50, 62, 83, 90, 115, 134），查找90的成功查找次数是2次，因为90位于第9个位置，而9是log2(11)向上取整的结果。同样，查找47需要进行3次查找，因为47位于第5个位置，而5是log2(11)向下取整的结果。如果查找100，由于100不在列表中，我们需要在找到最后一个元素134后才能确定不成功，所以查找次数是3次。 选择哪种查找方法取决于数据结构和查找效率的需求。顺序查找适合小规模或无序的数据集，而折半查找在有序数组中表现出更高的效率。理解并熟练掌握这些查找方法对于优化算法性能至关重要。