From: Robert Klemme <shortcutter@...>
Date: 2006-05-06T05:18:29+09:00
Subject: Re: Finding an interval in a sorted array?

2006/5/5, Robert Klemme <shortcutter@googlemail.com>:
> 2006/5/5, Bil Kleb <Bil.Kleb@nasa.gov>:
> > 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
>
> 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]

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

--
Have a look: http://www.flickr.com/photos/fussel-foto/