查找算法（JAVA）
·
一、查找算法的定义与分类
· 定义：在数据集合中寻找满足某种条件的数据元素的过程。
· 分类（Java中常用）：
1. 顺序查找（线性查找）
2. 二分查找（折半查找）
3. 插值查找
4. 斐波那契查找
二、查找算法的应用场景
· 学生信息管理系统（按学号/姓名查找）
· 图书馆图书检索
· 数据库查询优化
· 搜索引擎技术
· 各种数据结构（数组、链表、树等）中的查找操作
三、线性查找（顺序查找）
· 原理：从数据结构的一端开始，逐个比较每个元素，直到找到目标或遍历完所有元素。
· 步骤：
1. 从头开始遍历
2. 逐个比较
3. 找到则返回索引，否则返回-1
· 时间复杂度：
· 最坏：O(n)
· 平均：O(n)
· 最优：O(1)（第一个元素即为目标）
四、二分查找（折半查找）
· 前提：必须在有序数组中进行。
· 原理：每次取中间元素比较，根据比较结果缩小一半搜索范围，递归或迭代进行。
· 步骤：
1. 计算中间下标 mid = (left + right) / 2
2. 比较 arr[mid] 与目标值：
· 若相等，返回索引
· 若目标值大，向右查找
· 若目标值小，向左查找
3. 递归终止条件：找到目标或 left > right
· 时间复杂度：
· 平均：O(log n)
· 最优：O(1)（中间即为目标）
· 最坏：O(log n)
五、LeetCode 例题
· 两数之和（暴力法）：时间复杂度 O(n²)，建议使用哈希表优化至 O(n)
· 移动零：未展开讲解，但提示了查找算法的应用
六、练习
线性查找
二分查找
两数之和（暴力法）
移动零
更多推荐
21
0- 0
已为社区贡献4条内容
所有评论(0)