使用bsearch查找将新元素插入已排序数组的索引 [英] Using bsearch to find index for inserting new element into sorted array

问题描述

我有一个已排序的唯一数组，想要有效地将不在数组中的元素插入到这样的数组中:

I have a sorted unique array and want to efficiently insert an element into it that is not in the array like this:

a = [1,2,4,5,6]
new_elm = 3
insert_at = a.bsearch_index {|x| x > new_elm } # => 2
a.insert(insert_at, new_elm) # now a = [1,2,3,4,5,6]

方法bsearch_index不存在:只有bsearch，它返回匹配的元素而不是匹配元素的索引.有内置的方法可以做到这一点吗?

The method bsearch_index doesn't exist: only bsearch, which returns the matching element rather than the matching element's index. Is there any built in way to accomplish this?

推荐答案

您可以使用each_with_index返回的Enumerator对象返回[value, index]对的嵌套数组，然后对该数组进行二进制搜索:

You can use the Enumerator object returned by each_with_index to return a nested array of [value, index] pairs and then conduct your binary search on that array:

a = [1,2,4,5,6]
new_elm = 3

index = [*a.each_with_index].bsearch{|x, _| x > new_elm}.last
=> 2

a.insert(index, new_elm)

为了回答您的问题，我使用一些长度为1e6 - 1的数组运行了一些简单的基准测试:

I've run some simple benchmarks in response to your question with an array of length 1e6 - 1:

require 'benchmark'

def binary_insert(a,e)
  index = [*a.each_with_index].bsearch{|x, _| x > e}.last
  a.insert(index, e)
end

a = *1..1e6
b = a.delete_at(1e5)
=> 100001

Benchmark.measure{binary_insert(a,b)}
=> #<Benchmark::Tms:0x007fd3883133d8 @label="", @real=0.37332, @cstime=0.0, @cutime=0.0, @stime=0.029999999999999805, @utime=0.240000000000002, @total=0.2700000000000018> 

考虑到这一点，您可以考虑尝试使用堆或Trie而不是数组来存储值.堆尤其具有恒定的插入和移除时间复杂性，使其非常适合大型存储应用.在此处查看本文: Ruby算法:排序，特里和堆

With this in mind, you might consider trying using a heap or a trie instead of an array to store your values. Heaps in particular have constant insertion and removal time complexities, making them ideal for large storage applications. Check out this article here: Ruby algorithms: sorting, trie, and heaps

这篇关于使用bsearch查找将新元素插入已排序数组的索引的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！