From: FireAphis Date: 2007-10-03T17:15:12+09:00 Subject: Re: Searching through a sorted array On Oct 3, 9:56 am, "Axel Etzold" wrote: > -------- Original-Nachricht -------- > > > Datum: Wed, 3 Oct 2007 16:30:03 +0900 > > Von: Peter Szinek > > 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.