Ruby: Fastest way to test if any number from a list is in a list of ranges?

Question

One possible way to check if at least one number from a list is in one range of other list is like the following:

# Input example:
# numbers = [123, 345, 567]
# ranges =[(1..10), (60..80), (200..400)]
def is_in(numbers, ranges)
  numbers.each do |n|
    ranges.each do |r|
      return true if r.include?(n)
    end
  end
  false
end

What is the fastest way for each one of this cases:

1. Only numbers list is big
2. Only ranges list is big
3. Both are big

Answer 1

If your number array is large AND ordered, you could speed up the range coverage check from O(N) complexity to O(logN) using Ruby 2.0's new binary search Array#bsearch method.

class Range
  def fast_cover_any?(ordered_arr)
    lo = first
    probe = ordered_arr.bsearch {|x| x >= lo}
    probe && exclude_end? ? probe < last : probe <= last
  end
end

ranges.any? { |r| r.fast_cover_any?(numbers) }