知识卡片
二分插入点来自收敛边界
闭区间二分查找未命中并以 low>high 结束时,low 是保持升序的插入位置。不能直接使用最后一次中点 ix:例如查找比全部元素大的值,最后中点为 n−1,但插入位置为 n;空数组也没有最后中点。
若存在重复键且需要首个不小于目标的位置,应使用明确的 lower_bound 变种,而不是遇到相等即返回。数组插入仍可能移动 O(n) 元素;平衡树和页式 B 树适合不同的更新与存储访问需求。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
查找或者插入”操作,那么图5-2中第10行的ix最终值表示了缺失元素需要插入的索引值(所有较高的索引值都需要增加)。 二分查找有两个主要的变种。第一个和处理动态数据有关,在允许高效地插入或者删除时也需要维护一个可以接受的查找性能。如果集合是以数组的形式存储的话,因为每一个数组的条目都是一个有效的元素
参考来源
- 位置:《算法技术手册》第5章《变种》(spine1545;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1508.html;u124-ch05-006)。
- 结论依据:124全文与03249、03250终止逻辑对照实读。
- 原始内容:查找或者插入”操作,那么图5-2中第10行的ix最终值表示了缺失元素需要插入的索引值(所有较高的索引值都需要增加)。 二分查找有两个主要的变种。第一个和处理动态数据有关,在允许高效地插入或者删除时也需要维护一个可以接受的查找性能。如果集合是以数组的形式存储的话,因为每一个数组的条目都是一个有效的元素