Tag: big o

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）处获取值的索引？ （我的意思是数组已经排序了，我必须自己实现吗？） 谢谢。