知识卡片
有序范围可以反复折半
在按拼音顺序排列的字典中,比较中间位置与目标的先后关系,可以排除不可能的一半,再在剩余范围重复。这说明顺序信息可以换取更少的候选检查。
折半需要可判断的有序关系;无序集合不能仅靠中间元素排除半数。这里是二分查找的生活类比,精确区间边界和重复值处理在后续搜索章展开。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
查字典这个小学生必备技能,实际上就是著名的“二分查找”算法。从数据结构的角度,我们可以把字典视 为一个已排序的“数组”;从算法的角度,我们可以将上述查字典的一系列操作看作“二分查找” 。 例二:整理扑克。我们在打牌时,每
参考来源
- 位置:《Hello 算法--Go版本》第01章《初识算法》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/1.html;spine 0,归一字符[14624,14734))
- 结论依据:原文用字典中点比较缩小区间,图13展示实际步骤;不补造缺失拼音字母。
- 原始内容:查字典这个小学生必备技能,实际上就是著名的“二分查找”算法。从数据结构的角度,我们可以把字典视 为一个已排序的“数组”;从算法的角度,我们可以将上述查字典的一系列操作看作“二分查找” 。 例二:整理扑克。我们在打牌时,每