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

Question

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

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

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

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

做这个的最好方式是什么？使用散列在处理范围作为键时存在问题，并且使用case语句很难动态采用 to a。

Answer 1

如果您想要对数复杂度，则需要使用二分搜索或某种平衡搜索树。为简单起见，我建议使用rbtreegem：

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

Answer 2

即将到来的完美工作Range#bsearch:-) 这样您就可以获得正确的日志复杂性。

bsearch设置为在您想要最大值时找到最小值，因此您需要反转数组。享受：

DATA = [[2, :foo], [5, :bar], [12, :hello], [17, :baz]].reverse

def lookup(i)
  nb, val = DATA.bsearch{|nb, val| i >= nb}
  val
end

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

今天可用require 'backports/2.0.0':-)

Answer 3

我并没有真正理解哈希的问题，但如果我理解正确的话，这可以正常工作。

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

class Hash
  def get(i)
    return nil if i < keys.min
    i -= 1 until include?(i)
    self[i]
  end
end

h.get(4) #=> :foo
h.get(5) #=> :bar
h.get(1) #=> nil # No key below 2 exists.