algorithm - 快速插入有序数组

Question

我计划使用数组实现二分搜索——但是我还需要支持动态更新/插入到数组中。到目前为止，我听到的最好的方法是在 O(n) 范围内，因为插入点右侧的所有元素都需要向右移动一个。

我考虑过这个想法:我重新定义/拦截(或根据您的语言“重载”)插入方法 - 例如，如果检测到插入到索引 10，我“延迟”这个插入，我保持新元素第二个列表。实际数组中没有插入任何内容，但算法会记住插入点。其他插入也一样。然后，如果我检测到对元素 15 的访问，我也拦截了它，我会重新计算，将索引向右偏移 1，并给出元素 16，因为在 i=15 左侧的位置有一个插入。

偶尔我会通过将它们真正插入到真实列表中来清空第二个列表，可能是通过插入排序。

在我看来，它可以快速运行。

这可行吗？

谢谢，

Answer 1

我很确定您所看的方向没有什么好东西。我过去做过类似的事情，但前提是存在一种已知的访问模式使其变得高效。

如果您想保留数组存储和二分查找的一些效率，同时仍然允许动态插入，B+ 树是一个很好的权衡:

https://en.wikipedia.org/wiki/B%2B_tree

在 B+ 树中，每个节点都有一个键数组。您选择最大长度——通常在 16 到 4096 之间的任何地方。数组存储限制了浪费，因为您没有一大堆额外的链接，有助于在搜索期间缓存局部性，并提供限制树深度的高扇出。