优化顺序查找与折半查找：提高查找效率

"408二轮-查找.pdf" 这篇文档主要探讨了查找算法在顺序表和有序表中的应用，特别提到了顺序查找和折半查找两种方法，并涉及到了查找长度、平均查找长度（ASL）等相关概念。下面将详细阐述这些知识点。 1. **顺序查找**： - 顺序查找是一种基础的查找方法，适用于任何无序或有序的数据集合。在顺序查找中，从数据集合的第一个元素开始，逐个比较目标值与当前元素，直到找到目标或者遍历完整个集合。 - 示例代码展示了顺序查找的实现：从数组`S.T.elem[]`中查找键值`key`，如果找到则返回索引，否则返回-1。 - 优化：为了提高效率，可以考虑在已知部分数据分布的情况下，调整数据顺序，使查找概率较高的元素位于前面，但这需要额外的预处理。 2. **折半查找**： - 折半查找，也称为二分查找，仅适用于有序的序列。它利用了序列的排序特性，每次将查找区间减半，从而减少查找次数。 - 折半查找的示例代码显示了如何通过比较中间元素与目标值来调整查找范围，直至找到目标或确定不存在。 - 时间复杂度：折半查找的时间复杂度为O(log n)，比顺序查找更高效。当`mid`等于`low + (high - low) / 2`时，表示中间元素为查找目标或不存在。 3. **平均查找长度(ASL)**： - ASL是衡量查找效率的重要指标，包括成功查找的平均长度和失败查找的平均长度。 - 对于顺序查找，ASL成功时通常等于序列长度的平均值，失败时为序列长度。 - 折半查找的ASL成功时是一个几何级数的和，失败时则根据查找过程中失败结点的位置计算。例如，一个高度为h的判定树，其ASL可以通过计算各层节点的贡献来求得。 4. **平衡判定树**： - 平衡判定树是一种特殊的二叉搜索树，其中任意两个叶子节点之间的高度差不超过1。这确保了查找效率的稳定。 - 在折半查找的判定树中，如果`mid`等于`low + (high - low) / 2`，则表示找到了一个中间节点，这个节点可能是成功查找的终点，也可能意味着需要在子树中继续查找。 5. **查找概率与ASL**： - 当不同元素的查找概率不相等时，优化ASL的方法是将查找概率大的元素提前，这样可以提高成功查找的ASL，而失败查找的ASL保持不变。 本文档主要介绍了顺序查找和折半查找两种查找方法的原理、实现以及它们在实际应用中的优化策略，同时也涉及到了平均查找长度的概念及其在不同查找策略下的计算方法。对于理解查找算法和优化查找效率有很好的指导作用。