- 目标
- 仍有可能
- 比较中
- 已排除
- 已找到
二分查找
二分查找总是看中间,以此在有序列表中找到一个值。如果中间值太小,目标只可能在它之后;如果太大,只可能在它之前。无论哪种情况,剩余部分的一半都会被排除。选择要查找的值,逐步执行查找,看阴影部分不断缩小,直到找到目标或什么都不剩。 按“播放”观看查找过程,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到任意位置。虚线标出要查找的值,阴影部分是它仍可能所在的范围。二分查找需要有序列表,所以未排序的列表会先排序。可选择要查找的值、柱子数量,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。
它是如何运作的
- 选择要查找的值和柱子数量。也可以输入自己的数字:二分查找会先对它们排序。
- 按“播放”,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到查找的任意位置。
- 查找靠近末尾的值或不存在的值,对比“比较”卡片和“线性搜索需要”卡片。
二分查找的原理
记住有序列表中仍可能包含目标的部分;一开始就是整个列表。看这部分中间的值。如果等于目标,就完成了。如果较小,目标只可能在它之后,于是继续查找中间之后的部分。如果较大,就继续查找之前的部分。如果什么都不剩,说明目标不在列表中。
为什么这么快
每次比较都让剩余部分减半。从 n 个值开始,k 次比较后最多剩下约 n/2ᵏ 个,所以查找最多经过 ⌊log₂ n⌋ + 1 次比较就会结束:40 个值需要 6 次,1000 个需要 10 次,一百万个需要 20 次。线性搜索可能要查看每一个值。代价是列表必须有序,而保持有序或先排序本身也有成本。
常见问题
二分查找是怎么工作的?
它把目标与有序列表中仍可能包含目标的那部分的中间值比较。相等就是找到了;否则丢弃不可能包含目标的那一半,在另一半中继续查找,直到找到目标或什么都不剩。
二分查找需要多少次比较?
对 n 个值的列表最多 ⌊log₂ n⌋ + 1 次:40 个值需要 6 次,1000 个需要 10 次,一百万个需要 20 次。每次比较都让剩余部分减半。
为什么二分查找需要有序列表?
因为只有在有序列表中,一次比较才能告诉你目标在哪一边。在无序列表中,中间值较小并不能说明目标在哪里,因此什么也排除不了。
有重复值时会找到哪一个?
其中任意一个,取决于中间位置落在哪里。匹配后继续向左或向右查找的变体,可以找到第一个或最后一个出现的位置。
我的数字会被发送到别处吗?
不会。查找在你的浏览器中运行,上次的设置保存在本浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器