知识卡片

普通读书笔记卡 · 5626.e

有序范围可以反复折半

理解等级:中级

在按拼音顺序排列的字典中,比较中间位置与目标的先后关系,可以排除不可能的一半,再在剩余范围重复。这说明顺序信息可以换取更少的候选检查。

折半需要可判断的有序关系;无序集合不能仅靠中间元素排除半数。这里是二分查找的生活类比,精确区间边界和重复值处理在后续搜索章展开。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      查字典这个小学生必备技能,实际上就是著名的“二分查找”算法。从数据结构的角度,我们可以把字典视 为一个已排序的“数组”;从算法的角度,我们可以将上述查字典的一系列操作看作“二分查找” 。 例二:整理扑克。我们在打牌时,每

    参考来源

    - 位置:《Hello 算法--Go版本》第01章《初识算法》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[14624,14734)) - 结论依据:原文用字典中点比较缩小区间,图13展示实际步骤;不补造缺失拼音字母。 - 原始内容:查字典这个小学生必备技能,实际上就是著名的“二分查找”算法。从数据结构的角度,我们可以把字典视 为一个已排序的“数组”;从算法的角度,我们可以将上述查字典的一系列操作看作“二分查找” 。 例二:整理扑克。我们在打牌时,每