知识卡片
顺序查找无需预先建立索引
从集合起点逐个检查元素,匹配时返回,迭代结束仍未匹配则报告不存在。它适用于小集合、单次查找或只有顺序访问的输入;代价最坏为 n 次比较,首次命中为常数,未命中必须检查所有元素。
多次查找时,排序或索引可能降低查询成本,但还要考虑构建和更新开销;比较单个元素本身的成本也可能不恒定。
110的图03242分别给出数组和迭代器版本,均在找到相等元素时返回true,耗尽后返回false;空集合自然返回false。
111指出仅能顺序遍历时适合顺序查找;如果允许额外构建索引或缓存,后续查询仍可能有其他方案,取决于访问和更新约束。
113展示Ruby、Java和C实现:Ruby使用each与==;Java调用元素equals,若元素为null会抛异常;C以比较函数返回0代表相等,示例中的ar与n需由上下文提供。
115在目标必定存在且每个位置等可能的前提下得到 (n+1)/2 次比较;有未命中概率时还要计入每次 n 次比较。最好首次命中 O(1),最坏 O(n);03248为特定实验的历史时间。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 顺序查找无需预先建立索引
- · 输入/输出
- · 使用环境
- · 解决方案
- · 分析
原书出处 · 5 处
- · 查看原书依据
顺序查找 顺序查找也叫做线性查找,是最简单的查询算法。它通过穷举来寻找集合C中的单独目标元素t。它从集合中的第一个元素开始查找,然后检查每一个随后的元素,知道匹配的元素查找到或者集合中每一个元素都被查找过。 考虑这样一个案例,一个中等规模的饭店有10~20张桌子可以被顾客预定。这个饭店靠近一个大型的
- · 查看原书依据
输入/输出 肯定有多种方法来从查找的集合中获取元素,顺序并不重要。如果一个集合A支持索引,那么能用索引值i来获得元素A[i]。一个集合C通常只能通过一个只读的迭代器来获得其中的每一个元素(例如,一个和SQL查询语句相关数据库的游标)。使用游标存取这些元素的方法在图5-1的下半部描述。 输入 输入包括
- · 查看原书依据
迭代器来存取,并且一次只能返回集合中的一个元素,那么顺序查找就是你能使用的唯一查找算法。
- · 查看原书依据
Ruby代码。 例5-1:Ruby的顺序查找 代码是如此的简单。这个函数的输入是一个集合和需要寻找的目标元素。集合可以是个数组或者是Ruby中任何一种能够支持each方法的集合。查找中的元素必须支持==操作符;否则的话,你需要使用Ruby支持的其他类型的相等操作符。例5-2是相同例子的Java实现。
- · 查看原书依据
平均情况下顺序查找(如我们在第2章所述)。 也就是说,对于每个目标元素来说,你将需要寻找集合中大约一半的元素。最好情况即待查找的元素是集合中的第一个。算法在最坏和平均情况下都是线性增长的。如果你加倍集合的大小,那么查找的时间也大约会是两倍。 为了得到顺序查找的实际性能,我们构造了一个包含n个整数(范