知识卡片
上界位置帮助确定最右匹配
找首个大于target的位置,再退一格并检查相等性,就得到最右匹配。这个上界与首个不小于target的下界一起,可描述一整段相等元素。
原书以整数target+1复用下界,只有加法不溢出且值域离散时才成立;target±0.5转浮点也可能损失大整数精度。更通用的做法直接使用大于target的比较条件,不人为造一个邻近值。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
复用查找左边界 实际上,我们可以利用查找最左元素的函数来查找最右元素,具体方法为:将查找最右一个target 转化为查 找最左一个target + 1 如图10‑7 所示,查找完成后,指针 指向最左一个 (如果存在),而
参考来源
- 位置:《Hello 算法--Go版本》第10章《搜索》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[14684,14794))
- 结论依据:实际右边界复用和±0.5方法,限定溢出/精度并解释原始比较目标。
- 原始内容:复用查找左边界 实际上,我们可以利用查找最左元素的函数来查找最右元素,具体方法为:将查找最右一个target 转化为查 找最左一个target + 1 如图10‑7 所示,查找完成后,指针 指向最左一个 (如果存在),而