查找

查找是在数据集合中定位目标元素的过程。不同数据结构适合不同查找方式。

一、顺序查找

顺序查找从头到尾逐个比较。

特点：

• 实现简单；
• 适合无序数据；
• 时间复杂度 O(n)。

二、二分查找

二分查找适合有序数组。

特点：

• 时间复杂度 O(log n)；
• 要求数据有序；
• 适合顺序存储结构。

核心边界：

left = 0
right = n - 1
while left <= right

三、哈希查找

哈希查找通过哈希函数把 key 映射到数组下标。

特点：

• 平均复杂度 O(1)；
• 需要处理哈希冲突；
• 空间换时间。

冲突处理方式：

• 开放地址法；
• 链地址法；
• 再哈希。

四、树表查找

二叉搜索树、平衡树、B 树、B+ 树都属于树表查找。

适合：

• 动态插入删除；
• 有序遍历；
• 范围查询。

五、选择建议

场景	推荐方式
小规模无序数据	顺序查找
有序数组	二分查找
快速 key-value 查询	哈希查找
动态有序数据	平衡树
数据库索引	B+ 树

六、练习

• 实现顺序查找。
• 实现二分查找。
• 实现简单哈希表。
• 比较不同查找方式的性能。