---
title: 查找
tags:
  - module
  - data-structure-and-algorithm
  - search
  - joplin
type: module
source_type: reconstructed
created: 2026-04-22
updated: 2026-04-22
---

# 查找

> [!abstract]
> 这一模块处理“如何快速找到目标元素”这个核心问题。复习时重点不是背函数名，而是理解不同查找方式对数据有序性和结构的依赖。

## 模块结论

- [[查找算法]] 的核心是利用已有结构信息减少比较次数。
- 顺序查找适用范围最广，但效率通常较低。
- 折半查找要求有序顺序表，这是它高效的前提，不是白来的。

## 一、顺序查找

- 从头到尾逐个比较。
- 优点是实现简单，对存储结构要求低。
- 缺点是平均比较次数较多。

## 二、折半查找

- 要求表有序且支持随机访问。
- 每次比较后把查找区间缩小一半。
- 典型复杂度是 `O(log n)`。

### 为什么链表不适合折半查找

- 因为折半查找依赖快速定位中间位置。
- 链表访问中间结点代价高，无法发挥折半优势。

## 三、查找结构与查找代价

- 静态查找更关注查找效率。
- 动态查找还要考虑插入删除成本。
- 所以不同结构会引出顺序表、二叉排序树、平衡树、哈希等不同方案。

## 四、查找判定思维

- 先看数据是否有序。
- 再看是否允许随机访问。
- 最后看结构是静态还是动态变化。

## 五、易错点

- 折半查找快，不代表它适用所有场景。
- 有序只是条件之一，还要有合适的存储结构。
- 动态查找时不能只看一次查询速度，还要看维护代价。

## 六、复习提问

- 折半查找为什么要求有序顺序表？
- 查找问题为什么会引出树结构而不止是数组？
- 静态查找和动态查找各自更关注什么？

## 来源

- [[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/4.查找.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/5.二叉排序树.md]]
- [[raw/Joplin/计算机专业基础/数据结构与算法/(C++)数据结构与算法/12.二叉排序树.md]]

## 相关页面

- [[数据结构与算法]]
- [[查找算法]]
- [[二叉排序树]]
- [[AVL树]]