14.4.1 查找算法知识点概述

查找算法解决的是“给定关键字，判断表中是否存在并找到位置”。软考主要关注顺序查找、二分查找和哈希查找。它们的差异来自数据是否有序、是否支持随机访问、是否能直接通过函数定位。

查找算法对比

查找方式	前提	平均效率	核心思想
顺序查找	无序/有序均可	$O(n)$	从头到尾逐个比较
二分查找	有序顺序表	$O(\log n)$	每次排除一半
哈希查找	有散列函数	理想接近 $O(1)$	由关键字直接计算地址

先判断前提

题干条件	优先考虑
“无序表”	顺序查找
“有序顺序表”	二分查找
“链表”	通常不能直接二分
“散列函数/冲突/装填因子”	哈希表

技术迭代的理解

方法	优点	缺点	为什么有后继方法
顺序查找	最通用，不要求有序	数据量大时慢	希望减少比较次数
二分查找	查找次数少	要求有序且能随机访问	插入维护有序有成本
哈希查找	理想情况下很快	冲突处理复杂，范围查询弱	用空间和散列设计换速度

本节例题

单选

二分查找最基本的适用对象是：

A无序链表B有序顺序表C任意栈D任意队列

自查清单

1. 能否根据题干前提选择查找算法？
2. 能否说明二分查找为什么不适合普通链表？
3. 能否解释哈希查找为什么理想情况下接近 $O(1)$？