知识卡片
二分边界约定必须成套
二分查找每轮保持目标仍可能存在于当前区间,比较中点后排除不可能部分。闭区间以i≤j继续,排除中点时更新为m±1;左闭右开以i继续,排除右侧时把右界设为m。
初始化、空区间条件和更新规则必须来自同一约定,混用容易漏查或不缩小。中点用i+(j-i)/2降低有效非负索引相加的溢出风险,不能把两个模板的某一行孤立替换。
分治章用递归表达相同闭区间:空区间返回-1,比较后只返回选定子问题结果。每次缩半的路径深度为对数,递归版本还需相应栈;不能把迭代常数辅助空间直接套过来。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 2 处
- · 查看原书依据
在两种区间表示下,二分查找算法的初始化、循环条件和缩小区间操作皆有所不同。 由于“双闭区间”表示中的左右边界都被定义为闭区间,因此通过指针 和指针 缩小区间的操作也是对称 的。这样更不容易出错,因此一般建议采用“双闭区间
- · 查看原书依据
return dfs(nums, target, m+1, j ) 第12 章 分治 hello‑algo.com 267 } else if nums[m] > target { // 小于则递归左半数组 // 递归子
参考来源
- 位置:《Hello 算法--Go版本》第10章《搜索》(来源项目book-sources:extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/5.html;spine 4,归一字符[10810,10920))
- 结论依据:实际两套完整代码及图10-3支持边界不变量,空输入也自然为空区间。
- 原始内容:在两种区间表示下,二分查找算法的初始化、循环条件和缩小区间操作皆有所不同。 由于“双闭区间”表示中的左右边界都被定义为闭区间,因此通过指针 和指针 缩小区间的操作也是对称 的。这样更不容易出错,因此一般建议采用“双闭区间
补充原书证据:spine 5 / extracted/Hello 算法--Go版本/_epub-src/OEBPS/Text/6.html;归一字符[14047,14157)。
- 结论依据:实际递归二分尾部与入口补充实现形式和空间区别。
- 原始内容:return dfs(nums, target, m+1, j ) 第12 章 分治 hello‑algo.com 267 } else if nums[m] > target { // 小于则递归左半数组 // 递归子