比较
仍有可能
线性搜索需要

  • 目标
  • 仍有可能
  • 比较中
  • 已排除
  • 已找到

更多关于二分查找

二分查找

二分查找总是看中间,以此在有序列表中找到一个值。如果中间值太小,目标只可能在它之后;如果太大,只可能在它之前。无论哪种情况,剩余部分的一半都会被排除。选择要查找的值,逐步执行查找,看阴影部分不断缩小,直到找到目标或什么都不剩。 按“播放”观看查找过程,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到任意位置。虚线标出要查找的值,阴影部分是它仍可能所在的范围。二分查找需要有序列表,所以未排序的列表会先排序。可选择要查找的值、柱子数量,或输入自己的数字。选中画板后,方向键单步前进或后退,空格键播放和暂停,Home 和 End 键跳到开头和结尾。

它是如何运作的

  1. 选择要查找的值和柱子数量。也可以输入自己的数字:二分查找会先对它们排序。
  2. 按“播放”,或用“单步”和“后退”逐步前进。拖动步骤滑块可跳到查找的任意位置。
  3. 查找靠近末尾的值或不存在的值,对比“比较”卡片和“线性搜索需要”卡片。

二分查找的原理

记住有序列表中仍可能包含目标的部分;一开始就是整个列表。看这部分中间的值。如果等于目标,就完成了。如果较小,目标只可能在它之后,于是继续查找中间之后的部分。如果较大,就继续查找之前的部分。如果什么都不剩,说明目标不在列表中。

为什么这么快

每次比较都让剩余部分减半。从 n 个值开始,k 次比较后最多剩下约 n/2ᵏ 个,所以查找最多经过 ⌊log₂ n⌋ + 1 次比较就会结束:40 个值需要 6 次,1000 个需要 10 次,一百万个需要 20 次。线性搜索可能要查看每一个值。代价是列表必须有序,而保持有序或先排序本身也有成本。

常见问题

二分查找是怎么工作的?

它把目标与有序列表中仍可能包含目标的那部分的中间值比较。相等就是找到了;否则丢弃不可能包含目标的那一半,在另一半中继续查找,直到找到目标或什么都不剩。

二分查找需要多少次比较?

对 n 个值的列表最多 ⌊log₂ n⌋ + 1 次:40 个值需要 6 次,1000 个需要 10 次,一百万个需要 20 次。每次比较都让剩余部分减半。

为什么二分查找需要有序列表?

因为只有在有序列表中,一次比较才能告诉你目标在哪一边。在无序列表中,中间值较小并不能说明目标在哪里,因此什么也排除不了。

有重复值时会找到哪一个?

其中任意一个,取决于中间位置落在哪里。匹配后继续向左或向右查找的变体,可以找到第一个或最后一个出现的位置。

我的数字会被发送到别处吗?

不会。查找在你的浏览器中运行,上次的设置保存在本浏览器的本地存储中。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

前往编辑器