MathGroup Archive 1998

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Space between different Cells
  • Next by Date: Re: Re: Integrate Bug?
  • Previous by thread: In which interval?
  • Next by thread: Re: In which interval?