快速插入有序数组
Fast Inserts Into Ordered Arrays
我计划使用数组实现二进制搜索 - 但是我还需要支持动态更新/插入到数组中。到目前为止，我听到的最好的方法是在 O(n) 范围内，因为插入点右侧的所有元素都需要向右移动一个。
我考虑过这个想法：我重新定义/拦截（或 "overload" 取决于您的语言）插入方法 - 例如，如果检测到插入到索引 10，我 "delay" 这个插入，我将新元素保留在第二个列表中。实际数组中没有插入任何内容，但算法会记住插入点。其他插入也一样。然后，如果我检测到对元素 15 的访问，我也拦截了它，我会重新计算，将索引向右偏移 1，并给出元素 16，因为在 i=15 左侧的位置有一个插入。
偶尔我会通过将它们真正插入到真实列表中来清空第二个列表，可能是通过插入排序。
在我看来，它可以快速运行。
这可行吗？
谢谢，
你没有澄清关于你的想法的一些关键信息，例如你的算法如何记住新插入值的插入点，二进制搜索如何处理新的（即延迟的）插入，以及如果有 N 个这样的插入，你如何处理。
在任何情况下，您都必须在某个时候将延迟插入与原始数组合并，这将花费 O(N) 时间，或者您必须运行 二进制搜索同时考虑了原始数组和新插入的等待列表。考虑到动态插入可能会导致在本身位于该辅助数组中的两个元素之间插入一个元素，我不确定您如何以系统的方式做到这一点。您可能会妥协访问 A 的任何元素的成本，即常规数组中的 O(1)，进而可能最终导致效率较低的二分搜索比 O(logN)。因此，对您想法的不完整定义的高级概述似乎不太可能在复杂性方面达到预期的结果。
根据其定义，二分搜索适用于有序容器和连续存储每个元素的数组）使得不可能在任何位置插入，然后在最坏的情况下，在小于O(N)的情况下重新排列顺序。
虽然这不是形式化的证明，但凭直觉，你可能会想到这种情况。每当你必须向数组 A 插入一个小于 A 中存在的所有元素的元素时，为了将来的二进制搜索操作能够在 A 上工作，你必须将它插入开头，以便保持 A下令。而当你在A的第一个位置插入这么小的元素时，你必须将A中所有存在的元素向右移动1，即O(N)，如果size A的被认为是N。（参见著名算法插入步骤中的类似过程insertion sort）
因此，除非您更改对使用数组的偏好，否则在插入数组时您将受制于 O(N) 时间复杂度限制。但是，如果您考虑使用平衡二叉搜索树（例如 Red-black tree, AVL tree），您可能会实现更快的插入平均时间复杂度，并且不会牺牲搜索元素的效率。当然，在这种情况下，您 运行 查找元素的算法更像是树遍历而不是二进制搜索。尽管如此，如果更高效的搜索和插入（和删除）操作对您来说比您使用的特定算法和数据结构更重要，那么在您的数据结构和算法首选项中进行这种更改应该是可以容忍的。
"Would this be workable?"：也许吧，但不太可能。
对于每次插入，您都必须查找待定插入列表并确定对插入点的更正。并且您必须将新密钥插入待定列表中。你又回到了原来的插入有序数组的问题，但数组较小。
如果计算插入次数，假设最大大小为 L 的挂起列表，您将执行 O(N) 次，总成本为 O(N.L)。所以你需要 L 比 O(1) 更好。
如果算上合并，您将执行 N/L 次合并，成本为 N/L.(N + L)。那么你需要L为Ω(N)。
这两个要求似乎不兼容。
请确保在您之前（可能在您出生之前）已经彻底调查了排序列表中的插入问题，并且没有采用基于待处理列表的合适解决方案。
相反，平衡搜索树被普遍用于动态排序的目的，并且已知它们是最优的，对于搜索、插入和删除操作具有 O(Log N) 的界限。
我很确定您所看的方向没有什么好东西。我过去做过类似的事情，但只有当存在一种已知的访问模式才能使其高效时。
如果您想保持数组存储和二进制搜索的一些效率，同时仍允许动态插入，B+ 树是一个很好的权衡：
https://en.wikipedia.org/wiki/B%2B_tree
在 B+ 树中，每个节点都有一个键数组。您选择最大长度——通常在 16 到 4096 之间的任何地方。数组存储限制了浪费，因为您没有一大堆额外的链接，有助于在搜索期间缓存局部性，并提供限制树深度的高扇出。
我计划使用数组实现二进制搜索 - 但是我还需要支持动态更新/插入到数组中。到目前为止，我听到的最好的方法是在 O(n) 范围内，因为插入点右侧的所有元素都需要向右移动一个。
我考虑过这个想法：我重新定义/拦截（或 "overload" 取决于您的语言）插入方法 - 例如，如果检测到插入到索引 10，我 "delay" 这个插入，我将新元素保留在第二个列表中。实际数组中没有插入任何内容，但算法会记住插入点。其他插入也一样。然后，如果我检测到对元素 15 的访问，我也拦截了它，我会重新计算，将索引向右偏移 1，并给出元素 16，因为在 i=15 左侧的位置有一个插入。
偶尔我会通过将它们真正插入到真实列表中来清空第二个列表，可能是通过插入排序。
在我看来，它可以快速运行。
这可行吗？
谢谢，
你没有澄清关于你的想法的一些关键信息，例如你的算法如何记住新插入值的插入点，二进制搜索如何处理新的（即延迟的）插入，以及如果有 N 个这样的插入，你如何处理。
在任何情况下，您都必须在某个时候将延迟插入与原始数组合并，这将花费 O(N) 时间，或者您必须运行 二进制搜索同时考虑了原始数组和新插入的等待列表。考虑到动态插入可能会导致在本身位于该辅助数组中的两个元素之间插入一个元素，我不确定您如何以系统的方式做到这一点。您可能会妥协访问 A 的任何元素的成本，即常规数组中的 O(1)，进而可能最终导致效率较低的二分搜索比 O(logN)。因此，对您想法的不完整定义的高级概述似乎不太可能在复杂性方面达到预期的结果。
根据其定义，二分搜索适用于有序容器和连续存储每个元素的数组）使得不可能在任何位置插入，然后在最坏的情况下，在小于O(N)的情况下重新排列顺序。
虽然这不是形式化的证明，但凭直觉，你可能会想到这种情况。每当你必须向数组 A 插入一个小于 A 中存在的所有元素的元素时，为了将来的二进制搜索操作能够在 A 上工作，你必须将它插入开头，以便保持 A下令。而当你在A的第一个位置插入这么小的元素时，你必须将A中所有存在的元素向右移动1，即O(N)，如果size A的被认为是N。（参见著名算法插入步骤中的类似过程insertion sort）
因此，除非您更改对使用数组的偏好，否则在插入数组时您将受制于 O(N) 时间复杂度限制。但是，如果您考虑使用平衡二叉搜索树（例如 Red-black tree, AVL tree），您可能会实现更快的插入平均时间复杂度，并且不会牺牲搜索元素的效率。当然，在这种情况下，您 运行 查找元素的算法更像是树遍历而不是二进制搜索。尽管如此，如果更高效的搜索和插入（和删除）操作对您来说比您使用的特定算法和数据结构更重要，那么在您的数据结构和算法首选项中进行这种更改应该是可以容忍的。
"Would this be workable?"：也许吧，但不太可能。
对于每次插入，您都必须查找待定插入列表并确定对插入点的更正。并且您必须将新密钥插入待定列表中。你又回到了原来的插入有序数组的问题，但数组较小。
如果计算插入次数，假设最大大小为 L 的挂起列表，您将执行 O(N) 次，总成本为 O(N.L)。所以你需要 L 比 O(1) 更好。
如果算上合并，您将执行 N/L 次合并，成本为 N/L.(N + L)。那么你需要L为Ω(N)。
这两个要求似乎不兼容。
请确保在您之前（可能在您出生之前）已经彻底调查了排序列表中的插入问题，并且没有采用基于待处理列表的合适解决方案。
相反，平衡搜索树被普遍用于动态排序的目的，并且已知它们是最优的，对于搜索、插入和删除操作具有 O(Log N) 的界限。
我很确定您所看的方向没有什么好东西。我过去做过类似的事情，但只有当存在一种已知的访问模式才能使其高效时。
如果您想保持数组存储和二进制搜索的一些效率，同时仍允许动态插入，B+ 树是一个很好的权衡：
https://en.wikipedia.org/wiki/B%2B_tree
在 B+ 树中，每个节点都有一个键数组。您选择最大长度——通常在 16 到 4096 之间的任何地方。数组存储限制了浪费，因为您没有一大堆额外的链接，有助于在搜索期间缓存局部性，并提供限制树深度的高扇出。