Re: In which interval?

*To*: mathgroup at smc.vnet.net*Subject*: [mg13330] Re: [mg13303] In which interval?*From*: wself at viking.emcmt.edu (Will Self)*Date*: Mon, 20 Jul 1998 02:49:52 -0400*Sender*: owner-wri-mathgroup at wolfram.com

Pal Lillevold asks: >Given N distinct real Intervals (x(i),x(i+1)); i=1,,,,N and a real >number R - in which interval is R located. In other words to identify >the unique value of i such that x(i)<=R<x(i+1). This is easy to do by >straight forward checking which value of the N i's which match the >inequalities. But this is very time-consuming when the number N is >large. Has anyone been confronted with this problem and resolved it >efficiently? I would highly appreciate any assistance. > >Thank you in advance and best regards. I think what would work well for you is some kind of binary search. Start with the list of endpoint of the intervals, { x[[1]], x[[2]], . . ., x[[n]] } and split it somewhere in the middle, and test this middle x[[k]] against the value of R. Then you would know which half of the list sandwiches R, and you can proceed to narrow it down. You could split the list pretty much right in the middle, but if R is near the end it might be quicker to split the list near the end, and if R is near the beginning, split the list near the beginning. That is the rationale for the definition of index in the code below. That would be just right if the intervals all had the same length; if they don't, I don't see how you could do any better anyway. There should be some error handling in this code, for example, if r lies outside the intervals. locate[x_List, r_]:= Module[ {k=1, j=Length[x], index=1}, While[!(x[[k]]<=r<x[[k+1]]), index = Floor[k+(j-k)(r-x[[k]])/(x[[j]]-x[[k]])]; If[x[[index]]<=r,k=index,j=index]]; index] Example: In[2]:= x=FoldList[Plus, 0, Table[Random[],{1000}]]; In[3]:= Length[x] Out[3]= 1001 In[4]:= x[[1001]] Out[4]= 501.673 In[6]:= locate[x,400]//Timing Out[6]= {0.05 Second, 793} In[7]:= x[[793]] Out[7]= 399.544 In[8]:= x[[794]] Out[8]= 400.401