From: "Jesús Gabriel y Galán" <jgabrielygalan@...>
Date: 2007-10-03T21:35:01+09:00
Subject: Re: Searching through a sorted array

On 10/3/07, FireAphis <FireAphis@gmail.com> wrote:
> > > I have a very big array of objects sorted by one of its numeric data
> > > members. During the flow of my application I need occasionally to get
> > > all the elements in a specific range.
> Sorry if my explanation has been misleading. The array isn't
> necessarily comprised of continuous or consecutive numbers. Moreover
> they don't necessarily start from zero. For example:
>
> my_array = [-100, -99, -2, 0, 3, 125, 1742, 1234568763]
>
> now I want to get all the elements bigger than 1 and smaller than
> 1000. AFAIK my_array[1..1000] doesn't help in this case.

Here is my try:

class Array
  # assumes a sorted array whose elements respond appropriately to <=>
  def subrange(lower, higher)
    low = find_index_lower(lower)
    high = find_index_higher(higher)
    if (low >= length) || (high < 0)
      []
    else
      self[low..high]
    end

  end

   # Finds the lowest index whose value is greater than the specified parameter
   # If all values in the array are lower, returns the index after the last one
   # If all values are higher, returns 0
   def find_index_lower(lower)
     return length if ((last <=> lower) == -1)
     return 0 if ((first <=> lower) == 1)
     low = 0
     high = self.length - 1
     while low < high
       index = low + (high - low) / 2
       element = self[index]
       test = element <=> lower
       case test
       when 0:
         return index + 1
       when -1:
         return (index + 1) if ((self[index+1] <=> lower) == 1)
         low = index + 1
       when 1:
         return (index) if ((self[index-1] <=> lower) <= 0)
         high = index - 1
       end
     end
   end

   # Finds the highest index whose value is lower than the specified parameter
   # If all values in the array are higher, returns -1
   # If all values are lower, returns length-1
   def find_index_higher(higher)
     return -1 if ((first <=> higher) >= 0)
     return length - 1 if ((last <=> higher) == -1)
     low = 0
     high = self.length - 1
     while low < high
       index = low + (high - low) / 2
       element = self[index]
       test = element <=> higher
       case test
       when 0:
         return index - 1
       when -1:
         return (index) if ((self[index+1] <=> higher) >= 0)
         low = index + 1
       when 1:
         return (index - 1) if ((self[index-1] <=> higher) == -1)
         high = index - 1
       end
     end
   end


 end

a = [5, 6, 7, 8, 9, 10, 14]
p a
puts "6 - 13: #{a.subrange(6,13).inspect}"
puts "5 - 15: #{a.subrange(5,15).inspect}"
puts "5 - 100: #{a.subrange(5, 100).inspect}"
puts "2 - 100: #{a.subrange(2, 100).inspect}"
puts "-1 - 100: #{a.subrange(-1, 100).inspect}"
puts "100 - 150: #{a.subrange(100,150).inspect}"
puts "1 - 2: #{a.subrange(1,2).inspect}"

require 'benchmark'

n = 10_000
Benchmark.bmbm do |x|
  x.report("Array subrange") {
    n.times {a.subrange(6,13)}
  }
end

-----------------------------------------------------------

$ ruby array_subrange.rb
[5, 6, 7, 8, 9, 10, 14]
6 - 13: [7, 8, 9, 10]
5 - 15: [6, 7, 8, 9, 10, 14]
5 - 100: [6, 7, 8, 9, 10, 14]
2 - 100: [5, 6, 7, 8, 9, 10, 14]
-1 - 100: [5, 6, 7, 8, 9, 10, 14]
100 - 150: []
1 - 2: []
Rehearsal --------------------------------------------------
Array subrange   0.220000   0.020000   0.240000 (  0.274937)
----------------------------------------- total: 0.240000sec

                     user     system      total        real
Array subrange   0.190000   0.010000   0.200000 (  0.227276)

Jesus.