# Finding an interval in a sorted array?

**URL:** <https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717>\
**Category:** Ruby\
**Created:** [May 5, 2006, 7:25pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717 "2006-05-05T19:25:59Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![Bil\_K](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/848f3c/32.png) [@Bil\_K](https://www.ruby-forum.com/u/Bil_K)\
**Post date:** [May 5, 2006, 7:25pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717/1 "2006-05-05T19:25:59Z")

</div>

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,

---

<div class="post-metadata">

**Author:** ![Bil\_K](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/848f3c/32.png) [@Bil\_K](https://www.ruby-forum.com/u/Bil_K)\
**Post date:** [May 5, 2006, 8:47pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717/2 "2006-05-05T20:47:24Z")

</div>

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.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
To: “ruby-talk ML” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
Sent: Friday, May 05, 2006 1:25 PM  
Subject: Finding an interval in a sorted array?

---

<div class="post-metadata">

**Author:** ![Bil\_K](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/848f3c/32.png) [@Bil\_K](https://www.ruby-forum.com/u/Bil_K)\
**Post date:** [May 5, 2006, 8:53pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717/3 "2006-05-05T20:53:38Z")

</div>

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](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

---

<div class="post-metadata">

**Author:** ![Bil\_K](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/848f3c/32.png) [@Bil\_K](https://www.ruby-forum.com/u/Bil_K)\
**Post date:** [May 5, 2006, 10:02pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717/4 "2006-05-05T22:02:03Z")

</div>

2006/5/5, Bil K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> ```
> 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

---

<div class="post-metadata">

**Author:** ![Bil\_K](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/848f3c/32.png) [@Bil\_K](https://www.ruby-forum.com/u/Bil_K)\
**Post date:** [May 5, 2006, 10:20pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717/5 "2006-05-05T22:20:35Z")

</div>

2006/5/5, Robert K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid):

> > ```
> > # 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

---

<div class="post-metadata">

**Author:** ![Bil\_K](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/b/848f3c/32.png) [@Bil\_K](https://www.ruby-forum.com/u/Bil_K)\
**Post date:** [May 10, 2006, 1:20pm UTC](https://www.ruby-forum.com/t/finding-an-interval-in-a-sorted-array/59717/6 "2006-05-10T13:20:28Z")

</div>

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,