-------- Original-Nachricht --------
> Datum: Wed, 3 Oct 2007 16:30:03 +0900
> Von: Peter Szinek <peter / rubyrailways.com>
> An: ruby-talk / 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 Modem und ISDN: http://www.gmx.net/de/go/smartsurfer