知识卡片

普通读书笔记卡 · 5626.e.1.b

上界位置帮助确定最右匹配

理解等级:中级

找首个大于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 所示,查找完成后,指针 指向最左一个 (如果存在),而