Ruby-在O（log n）运行时从sorted（唯一）数组中删除一个值

我有一个排序数组（唯一值，不重复）。

我知道我可以使用Array＃binarysearch但它用于查找值而不是删除它们。 我也可以删除O（log n）的值吗？ 怎么样？

让我说我有这个数组：

arr = [-3, 4, 7, 12, 15, 20] #very long array 

我想删除值7.到目前为止，我有这个：

 arr.delete(7) #I'm quite sure it's O(n) 

假设Array＃delete-at在O（1） 处工作。 我可以做arr.delete_at(value_index)现在我只需要获取值的索引。 二进制搜索可以做到这一点，因为数组已经排序。 但是利用排序属性（我所知道的）的唯一方法是二进制搜索，它返回值，而不是删除或返回索引。

把它们加起来：

1）如何在O（log n）处从已排序的非重复数组中删除值？

要么

2）假设数组#lele-at在O（1） 处工作（是吗？），如何在O（log n）处获取值的索引？ （我的意思是数组已经排序了，我必须自己实现吗？）

谢谢。

Answer 1

标准Array实现对排序或重复没有约束。 因此，默认实现必须灵活地交换性能。

Array#delete删除O(n)的元素。 这是C实现 。 注意循环

 for (i1 = i2 = 0; i1 < RARRAY_LEN(ary); i1++) { ... } 

由于Ruby必须扫描与给定值匹配的所有项目（注意delete删除与值匹配的所有条目，而不仅仅是第一个），然后将下一个项目移动到压缩数组，因此成本是合理的。

delete_at具有相同的成本。 实际上，它通过给定的索引删除元素，但是它使用memmove将剩余的条目在数组上减少一个索引。

使用二进制搜索不会改变成本。 搜索将花费您O(log n) ，但您需要删除给定键的元素。 在最坏的情况下，当元素处于位置[0] ，将存储器中的所有其他项目移位1个位置的成本将是O(n) 。

在所有情况下，成本为O(n) 。 这并不意外。 Ruby中的默认数组实现使用数组。 这是因为，如前所述，没有可用于优化运营的具体约束。 容易迭代和操作集合是首要任务。

数组，排序数组，列表和排序列表：所有这些数据结构都很灵活，但您需要在某些特定操作中支付成本。

回到你的问题，如果你关心性能并且你的arrays是有序的和独特的，你绝对可以利用它。 如果您的主要目标是从数组中查找和删除项目，则可以使用更好的数据结构。 例如，您可以创建一个使用d-heap在内部存储数组的自定义类，其中delete()成本为O(log[d,n]) ，如果使用二项式堆 ，则同样适用。