Finding an interval in a sorted array?

Ruby
1

Hello,

Surely there is a way to find an interval in a sorted array
without resorting to indices? (I’m drawing a blank.)

require ‘test/unit’

class Array
def interval_containing( x )
# elegant code goes here
end
end

class TestIntervalFinder < Test::Unit::TestCase
def test_finds_intervals
data = [ 0, 1, 2 ].sort
assert_equal [0], data.interval_containing(-0.2)
assert_equal [0], data.interval_containing( 0.0)
assert_equal [0,1], data.interval_containing( 0.5)
assert_equal [1], data.interval_containing( 1.0)
assert_equal [1,2], data.interval_containing( 1.6)
assert_equal [2], data.interval_containing( 2.0)
assert_equal [2], data.interval_containing( 5.0)
end
end

Thanks,

2

class Array
def interval_containing( x )
# elegant code goes here
[select{|e|e<=x}[-1], select{|e|e>=x}[0]].compact.uniq
end
end

% ruby tIntervalContaining.rb
Loaded suite tIntervalContaining
Started
.
Finished in 0.0 seconds.

1 tests, 7 assertions, 0 failures, 0 errors

best
Sergey

----- Original Message -----
From: “Bil K.” [email protected]
To: “ruby-talk ML” [email protected]
Sent: Friday, May 05, 2006 1:25 PM
Subject: Finding an interval in a sorted array?

3

On Sat, 6 May 2006, Bil K. wrote:

end
assert_equal [2], data.interval_containing( 2.0)
assert_equal [2], data.interval_containing( 5.0)
end
end

Thanks,

Bil
http://fun3d.larc.nasa.gov

this ought to get you going

class Array
#
# extract any sequences in a sorted list
#
# [0, 1, 2, 4, 5].sequences #=> [0…2, 4…5]
# [-5, -4, -4, -3, 0, 1].sequences #=> [-5…-4, -4…-3, 0…1]
#
def sequences list = self.sort
distance = lambda do |a,b|
(b - a).abs
end
continuous = lambda do |range, list|
first, last = range.first, range.last
a, b = list[first], list[last]
((list.empty? or (distance[a,b] == distance[first,last])) ? (a
… b) : nil)
end
discrete = lambda do |range, list|
first, last = range.first, range.last
edge = last + 1
(edge >= list.length or distance[list[last], list[edge]] != 1)
end
sequence = lambda do |range, list|
first, last = range.first, range.last
(list[first] … list[last])
end

   last = list.length - 1
   a, b = 0, last

   accum = []
   while a <= b and a < list.length and b < list.length
     range = a .. b

     if continuous[ range, list ]
       if discrete[ range, list ]
         accum << sequence[ range, list ]
         a, b = b + 1, last # move a and b up
       else
         b = b + (distance[b, last] / 2) # move b up
       end
     else
       b = a + (distance[a, b] / 2) # move b down
     end
   end
   accum
 end

end

i think you need to re-write your test since an array could have the
same
interval twice - eg test must be on a list of intervals

regards.

-a

4

2006/5/5, Bil K. [email protected]:

end
  assert_equal [2],   data.interval_containing( 2.0)
  assert_equal [2],   data.interval_containing( 5.0)
end

end

Solutions - of course with inject:

module Enumerable
def f1(x)
[inject(nil) {|a,b| return [a,b] if (a||x)<=x && b>x; b}, nil]
end

def f2(x)
inject {|a,b| return [a,b] if a<=x && b>x; b}
nil
end
end

irb(main):015:0> a=[0,1,2]
=> [0, 1, 2]
irb(main):016:0> a.f1 0.2
=> [0, 1]
irb(main):017:0> a.f2 0.2
=> [0, 1]
irb(main):018:0> a.f1 0
=> [0, 1]
irb(main):019:0> a.f1 -1
=> [nil, 0]
irb(main):020:0> a.f1 10
=> [2, nil]

Kind regards

robert

5

2006/5/5, Robert K. [email protected]:

  # elegant code goes here
  assert_equal [1,2], data.interval_containing( 1.6)

end
irb(main):016:0> a.f1 0.2
=> [0, 1]
irb(main):017:0> a.f2 0.2
=> [0, 1]
irb(main):018:0> a.f1 0
=> [0, 1]
irb(main):019:0> a.f1 -1
=> [nil, 0]
irb(main):020:0> a.f1 10
=> [2, nil]

PS: Sergey is right of course, you don’t need a sorted sequence. Here
is a bit more verbose and slightly more efficient approach:

module Enumerable
def f3(x)
lo = hi = nil
each do |n|
lo = n if n <= x && ( lo.nil? || n > lo )
hi = n if n > x && ( hi.nil? || n < hi )
end
[lo, hi]
end
end

irb(main):022:0> [2,1,0].f3 0.5
=> [0, 1]
irb(main):023:0> [2,1,0].f3 5
=> [2, nil]
irb(main):024:0> [2,1,0].f3 -1
=> [nil, 0]

Cheers

robert

6

Sergey V. wrote:

class Array
def interval_containing( x )
# elegant code goes here
[select{|e|e<=x}[-1], select{|e|e>=x}[0]].compact.uniq
end
end

My officemate prompted this question. Here’s his
“final answer”:

def interval_containing x
lower, upper = partition{|i| i <= x}
[lower.last, upper.first]
end

This leaves a nil in one of the slots if the interval is off one
of the ends, which might be what I want. To pass the tests,
the return value should be [lower.last, upper.first].uniq

Thanks for all the ideas,