Re: Efficient search for bounding list elements

*To*: mathgroup at smc.vnet.net*Subject*: [mg114181] Re: Efficient search for bounding list elements*From*: Barrie Stokes <Barrie.Stokes at newcastle.edu.au>*Date*: Fri, 26 Nov 2010 05:29:00 -0500 (EST)

Hi David I didn't quite understand Oliver Ruebenkoenig's answer to your question, so I looked at the documentation for Nearest, and ended up with: a = Range[1000, 5000, 250]; Map[ (s\[Function]Position[ a, s ]), Nearest[a, 1600, 2] ]//Flatten (Thanks, Oliver!) You might like to compare these timings with your loop approach: In[86]:= a=Range[1,500000,2]; Map[(s\[Function]Position[a,s]),Nearest[a,1600,2]]//Flatten//Timing Out[87]= {0.156,{800,801}} In[88]:= a=Range[1,5000000,2]; Map[(s\[Function]Position[a,s]),Nearest[a,1600,2]]//Flatten//Timing Out[89]= {1.528,{800,801}} Cheers Barrie >>> On 25/11/2010 at 9:58 pm, in message <201011251058.FAA21975 at smc.vnet.net>, David Skulsky <edskulsky at gmail.com> wrote: > I've been looking for a way to efficiently find the indices of the two > elements of a monotonically increasing list which bound a number. For > example, if > > a = Range[1000,5000,250] > > and > > x=1600 > > then I'd like this function (e.g., searchFunction[x,a]) to return > {3,4}, which correspond to the 3rd and 4th elements of a, which are > 1500 and 1750, respectively. > > I can easily do this in a loop, but in my application a can be very > large (hundreds of thousands or millions of elements) and this > operation needs to repeated thousands of times, so efficiency is > critical. > > Any suggestions would be greatly appreciated! > > Thanks, > > David Skulsky