From: 7stud -- <dolgun@...>
Date: 2007-10-03T20:45:50+09:00
Subject: Re: Searching through a sorted array

FireAphis wrote:
> My problem is that, as far as I know, find_all just iterates through
> all the elements of the array and that's very inefficient, especially
> in my case, in which I have a sorted array. Is there any standard way
> to search efficiently through a sorted array? A binary search for
> example?
> 

You can also turn your array into a hash, which will work just as well 
for unsorted arrays:


class Dog
  attr_reader :breed, :id

  def initialize(breed, id)
    @breed = breed
    @id = id
  end

end

#Create sorted array of Dog's:
#-----------------------------
dogs = []
(1..2_000).each do |r|
  dogs << Dog.new("Akita", r*2)
end

=begin
dogs = (1..2000).inject([]) do |arr, r|
  arr << Dog.new("Akita", r*2)
  arr
end
=end
#----------------------------+


#Convert array to hash.
#key: dog.id
#val: Dog object
#---------------------
my_id_dog_hash = {}

class << my_id_dog_hash
  attr_accessor :highest_id
end

dogs.each do |dog|
  my_id_dog_hash[dog.id] = dog
end

my_id_dog_hash.highest_id = dogs[-1].id
----------------------+


#Find Dog's in range:
#-------------------
def get_dogs_in_range(id_dog_hash, range)

  high_id = id_dog_hash.highest_id
  if range.end > high_id
    range = range.begin..high_id
  end


  dogs_in_range = []

  range.each do |r|
    dog = id_dog_hash[r]

    if dog
      dogs_in_range << id_dog_hash[r]
    end

  end
=begin
  dogs_in_range = range.inject([]) do |arr1, r|
    if dog = id_dog_hash[r]
      arr1 << dog
    end

    arr1
  end
=end

  dogs_in_range
end
------------------+


#Test it out:
------------
results = get_dogs_in_range(my_id_dog_hash, 1_990..2000)
results.each {|dog| p dog}
-----------+

--output:--
#<Dog:0x1a70c @id=1990, @breed="Akita">
#<Dog:0x1a6e4 @id=1992, @breed="Akita">
#<Dog:0x1a6bc @id=1994, @breed="Akita">
#<Dog:0x1a694 @id=1996, @breed="Akita">
#<Dog:0x1a66c @id=1998, @breed="Akita">
#<Dog:0x1a644 @id=2000, @breed="Akita">



-- 
Posted via http://www.ruby-forum.com/.