使用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,2,3,4,5,6] 

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

Answer 1

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

 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的数组运行了一些简单的基准来响应你的问题：

 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)} => # 

考虑到这一点，您可以考虑尝试使用堆或trie而不是数组来存储您的值。 特别是堆具有恒定的插入和移除时间复杂性，使其成为大型存储应用的理想选择。 在这里查看这篇文章： Ruby算法：排序，trie和堆

Answer 2

使用SortedSet怎么样？：

 require 'set' a = SortedSet.new [1,2,4,5,6] new_elm = 3 a << new_elm # now a = # 

---

SortedSet使用rbtree实现。 我做了以下基准测试：

 def test_sorted(max_idx) arr_1 = (0..max_idx).to_a new_elm = arr_1.delete(arr_1.sample) arr_2 = arr_1.dup set_1 = SortedSet.new(arr_1) Benchmark.bm do |x| x.report { arr_1.insert(arr_1.index { |x| x > new_elm }) } x.report { arr_2.insert([*arr_2.each_with_index].bsearch{|x, _| x > new_elm}.last) } x.report { set_1 << new_elm } end end 

结果如下：

 test_sorted 10_000 # => user system total real # => 0.000000 0.000000 0.000000 ( 0.000900) # => 0.010000 0.000000 0.010000 ( 0.001868) # => 0.000000 0.000000 0.000000 ( 0.000007) test_sorted 100_000 # => user system total real # => 0.000000 0.000000 0.000000 ( 0.001150) # => 0.000000 0.010000 0.010000 ( 0.048040) # => 0.000000 0.000000 0.000000 ( 0.000013) test_sorted 1_000_000 # => user system total real # => 0.040000 0.000000 0.040000 ( 0.062719) # => 0.280000 0.000000 0.280000 ( 0.356032) # => 0.000000 0.000000 0.000000 ( 0.000012) 

Answer 3

“方法bsearch_index不存在”：Ruby 2.3引入了bsearch_index 。 （在它存在之前获取方法名称的荣誉）。

Answer 4

试试这个

 (0...a.size).bsearch { |n| a[n] > new_element } 

这使用在Range上定义的bsearch来搜索数组，从而返回索引。

---

性能将优于each_with_index ，它实现了O(n)临时数组元组，从而阻塞了垃圾收集。

Answer 5

Ruby 2.3.1引入了bsearch_index，因此现在可以通过这种方式解决问题：

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

Answer 6

index方法接受一个块，并返回块为true的第一个索引

 a = [1,2,4,5,6] new_elem = 3 insert_at = a.index{|b| b > new_elem} #=> 2 a.insert(insert_at, new_elm) #=>[1,2,3,4,5,6]