- 目标
- 比较中
- 已排除
- 已找到
线性搜索
线性搜索是查找值最简单的方法:从头开始,逐个检查每个值,直到找到为止。它适用于任何列表,无论是否有序。选择要查找的值,播放搜索过程或逐次比较单步执行,观察比较次数如何取决于值的位置,以及值是否存在。 按“播放”观看搜索过程,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到任意位置。虚线标出要查找的值。可选择要查找的值、柱子数量、初始顺序,或输入自己的数字。关闭“找到第一个匹配就停止”可找出所有匹配。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择要查找的值、柱子数量和初始顺序。也可以输入自己的数字。
- 按“播放”,或用“单步”和“后退”逐次比较。拖动步骤滑块可跳到搜索的任意位置。
- 关闭“找到第一个匹配就停止”,可检查每个值并找出所有匹配。
线性搜索的原理
把第一个值与目标值比较。如果相等,就完成了。如果不等,就看第二个值,然后第三个,依此类推。如果到了列表末尾仍没有匹配,目标值就不在列表中。无需任何准备:列表不必有序。
比较次数
第 k 位的值经过 k 次比较找到。最好情况是一次比较,即目标值在第一位。最坏情况是 n 次,即目标值在最后或不存在,因为只有检查完每个值,才能确定它不在列表中。对于在列表中的值,平均约需 (n + 1)/2 次比较。对于有序列表,二分查找要好得多:约 log₂ n 次比较,40 个值时只需 6 次,而不是最多 40 次。
常见问题
线性搜索如何工作?
它从第一个到最后一个,逐个检查列表中的值,直到找到目标值或检查完所有值。它也叫顺序查找。
线性搜索的时间复杂度是多少?
O(n):最坏情况下(目标值在最后或不存在),要把目标值与全部 n 个值比较。对于在列表中的目标值,平均约需 (n + 1)/2 次比较。
什么时候适合用线性搜索?
适用于短列表、未排序且只查找一两次的列表,以及只能按顺序读取的数据,比如数据流。先排序再用二分查找,只有在需要多次查找时才划算。
为什么不存在的值代价最大?
因为没有什么能让线性搜索提前停止。只有检查完每个值,才能排除匹配,所以不在列表中的值总要 n 次比较。
我的数字会被发送到别处吗?
不会。搜索在你的浏览器中运行,最近的设置保存在此浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器