查找

概述

查找是在数据集中寻找满足条件的元素，目标是降低比较次数和时间复杂度。

常见查找方式

• 顺序查找：适用于无序或规模较小的数据。
• 二分查找：要求数据有序，时间复杂度 $O(\log n)$。
• 哈希查找：通过散列函数直接定位，平均时间复杂度接近 $O(1)$。
• 树结构查找：如二叉搜索树、平衡树。

评价指标

• 平均查找长度（ASL）。
• 成功/失败查找的比较次数。

相关概念

• 关键字：用于比较的属性或字段。
• 装填因子：哈希表中元素数量与桶数量的比例。