ruby – 使用bsearch查找将新元素插入到排序数组中的索引

发布时间：2020-12-16 20:57:08 所属栏目：百科来源：网络整理

导读：我有一个排序的唯一数组,并希望有效地插入一个不在数组中的元素,如下所示： a = [1,2,4,5,6]new_elm = 3insert_at = a.bsearch_index {|x| x new_elm } # = 2a.insert(insert_at,new_elm) # now a = [1,3,6] 方法bsearch_index不存在：只有bsearch,它返回匹

我有一个排序的唯一数组,并希望有效地插入一个不在数组中的元素,如下所示：

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,3,6]

方法bsearch_index不存在：只有bsearch,它返回匹配元素而不是匹配元素的索引.有没有内置的方法来实现这一目标？

解决方法

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

a = [1,6]
new_elm = 3

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

a.insert(index,new_elm)

编辑：

我用一个长度为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 algorithms: sorting,trie,and heaps

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!