From: Axel Etzold <AEtzold@...>
Date: 2007-10-03T18:15:07+09:00
Subject: Re: Searching through a sorted array


-------- Original-Nachricht --------
> Datum: Wed, 3 Oct 2007 17:15:12 +0900
> Von: FireAphis <FireAphis@gmail.com>
> An: ruby-talk@ruby-lang.org
> Betreff: Re: Searching through a sorted array

> On Oct 3, 9:56 am, "Axel Etzold" <AEtz...@gmx.de> wrote:
> > -------- Original-Nachricht --------
> >
> > > Datum: Wed, 3 Oct 2007 16:30:03 +0900
> > > Von: Peter Szinek <pe...@rubyrailways.com>
> > > An: ruby-t...@ruby-lang.org
> > > Betreff: Re: Searching through a sorted array
> > > FireAphis wrote:
> > > > Hello,
> >
> > > > 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.
> >
> > > Then why not
> >
> > > my_array[start..end] ?
> >
> > Dear FireAphis,
> >
> > to find the values 'start' and 'end', you could use something like
> > the twenty questions game to find a number between 1 and a million
> > (roughly 2^20, hence 20 questions), starting by :
> >
> > 1.) Is the index of 'start' ('end') bigger or smaller than 2^19 (roughly
> 500000)?
> >
> > 2.) If the answer was "yes", is the index of 'start' ('end') bigger or
> smaller than 2^19+2^18 (roughly 750000)?
> > If the answer was "no", is the index of 'start' ('end') bigger or
> smaller than 2^18 (roughly 250000)?
> >
> > etc..
> >
> > The range in which "start" lies reduces its  size by half with each
> question, and you need 2*log(2) n questions to find the 'start' and 'end'
> > values.
> >
> > I am actually not aware whether that's implemented in the Array#index
> > method.
> >
> > Best regards,
> >
> > Axel
> >
> > --
> > Der GMX SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen!
> > Ideal f�r Modem und ISDN:http://www.gmx.net/de/go/smartsurfer
> 
> Of course that could be an excellent solution. Do you know if there is
> already such a facility in Ruby that implements the algorithm? I'm
> quite sure Array#index doesn't do that since in order to apply a
> binary search the array has to be sorted.
> 

Dear FireAphis,

I don't know of an implemented solution, but I've implemented my own ... use at your own risk!

Best regards,

Axel 


class Array
	def find_lower_index(cond)
		len=self.length
		upper=len
		max_nr=(Math.log(len)/Math.log(2)).floor
		lower_index=0
		pow=1
		while eval(cond)==false
			lower_index=2**pow
			pow=pow+1
		end
		pow=pow-2
		lower=2**pow
		(pow-1).downto(0) do |x|
			old_test=lower_index
			lower_index=lower+2**x
			if eval(cond)==false
			else
				lower_index=old_test
			end
		end
		return lower_index+1
	end
	
	def find_upper_index(cond)
		len=self.length
		upper=len
		max_nr=(Math.log(len)/Math.log(2)).floor
		upper_index=0
		pow=1
		while eval(cond)==true
			upper_index=2**pow
			pow=pow+1
		end
		pow=pow-2
		upper=2**pow
		(pow-1).downto(0) do |x|
			old_test=upper_index
			upper_index=upper+2**x
			if eval(cond)
			else
				upper_index=old_test
			end
			upper=upper_index
		end
		return upper_index-1
	end

	
end

# some example
len=10**8
a=(1..len).to_a
b=5*len/2
cond='lower_index>10'
r=a.find_lower_index(cond)
cond='upper_index<100'
s=a.find_upper_index(cond)
p r,s
p a[r]
p a[s]

-- 
Psssst! Schon vom neuen GMX MultiMessenger geh�rt?
Der kanns mit allen: http://www.gmx.net/de/go/multimessenger