ruby - 将数字序列转换为条件/范围

Question

我有一个由成对的数字和一些值组成的数组:

a = [[2, :foo], [5, :bar], ..., [17, :baz]]

其中可以假定没有两对具有相同的数字，并且这些对按其数字的值排序。基于这个数组a，我想传递一个数字i，它总是在a中的最小和最大数字之间，并返回与不超过i的最大数字配对的值。一些预期的返回值是:

2 # => :foo
4 # => :foo
5 # => :bar
17 # => :baz

最好的方法是什么？使用散列作为键处理范围存在问题，使用 case 语句难以动态采用 a。

Answer 1

如果您想要对数复杂度，则需要使用二分查找或某种平衡查找树。为简单起见，我建议 rbtree gem :

require 'rbtree'

a = [[2, :foo], [5, :bar], [17, :baz]]
t = RBTree[a]

t.upper_bound 4  # => [2, :foo]
t.upper_bound 5  # => [5, :bar]
t.upper_bound 1  # => nil