Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

How can one find the range in which a number falls, from given list of numbers?

f[x_, list_List] := ???
(*
Return {a,b} where
a & b belongs to list
{a,b} forms shortest possible interval which match condition
if a<=x<=b {a,b}
if x <= a {-∞,a}
if x >= b {b,∞}
*)

f Should also consider outer ranges $-\infty$ and $\infty $

share|improve this question
    
And what do you want to happen with f if x is an element of list? –  J. M. Jan 21 '12 at 10:16
    
it should return two ranges then –  Prashant Bhate Jan 21 '12 at 10:21
    
And when there is only one element in the list , and if it is x then it should return {{-∞,x},{x,∞}} –  Prashant Bhate Jan 21 '12 at 10:26

9 Answers 9

up vote 11 down vote accepted

I propose using Interpolation.

list = Prime~Array~3000;
intf = Interpolation[
         {list, Range@Length@list}\[Transpose],
         InterpolationOrder -> 0
       ];

Then, for point x:

x = 12225.4;

Which[
 x < First@list , {-\[Infinity], First@list},
 x > Last@list  , {Last@list, \[Infinity]},
 True           , list[[#-1 ;; #]]& @ intf @ x
]
{12211, 12227}

This could all be done inside Interpolation as well:

intf2 =
  Interpolation[
    Join[
      {{First@list, {-\[Infinity], 2}}},
      Thread[{Rest@list, Partition[list, 2, 1]}],
      {{Last@list + 1, {Last@list, \[Infinity]}}}
    ],
    InterpolationOrder -> 0
  ];

intf2[12225.4]
{12211, 12227}
share|improve this answer
    
Yet another non-obvious gem +1 –  kguler Jan 21 '12 at 13:05
2  
This method requires pre-sorted input data without duplicates. For an arbitrary list you need to pre-process the list with DeleteDuplicates@Sort or Union. Interpolation gives error messages when input data is unsorted or contains duplicates. –  kguler Jan 21 '12 at 16:06
    
@kguler Indeed. Thank you for stating that. I made assumptions on the meaning and structure of a "given list of numbers." –  Mr.Wizard Jan 22 '12 at 7:09

You can make use of BinCounts. I think this is a very simple to understand solution because BinCounts does almost exactly what you need already.

f[x_, list_List] :=
 Module[{bins},
  bins = Join[{-Infinity}, Sort[list], {Infinity}];
  First@Pick[Partition[bins, 2, 1], BinCounts[{x}, {bins}], 1]
 ]

But it won't give you two intervals if the number is part of both. Of course it's very easy to put in an extra check and include this feature if you need it, but I just wanted to show the concept now.

share|improve this answer
    
Cool.. I was trying to figure out how to use the third argument of Pick, This is a great example.+1 –  kguler Jan 21 '12 at 16:23

Assuming the list list is already ordered, the following should answer your question:

f[x_,list_List]:=
  Module[{pos=Last@Ordering@Ordering[Append[list,x]]},
    Which[pos==1,{-Infinity,First@list},
          pos==Length[list]+1,{Last@list,Infinity},
          True,list[[{pos-1,pos}]]]]
share|improve this answer

My favorite:

 interval[x_,list_List]:=ReplaceList[Append[Prepend[Sort@list, -Infinity], 
        Infinity], {___, a_, b_, ___} /; (a <= x <= b) :> {a, b}]

EDIT: Much faster if we eliminate the condition checking as follows:

 interval2[x_, list_List] := ReplaceList[#, {___, a_, x, b_, ___} :> {a, b}  ] &@
   Join[{-Infinity}, Sort[Join[list, {x}]], {Infinity}]
share|improve this answer
    
This is clever, but it is going to be quite inefficient. This is 10,000X slower than InterpolatingFunction on the data in my answer. This may or may not matter, but it should be noted. –  Mr.Wizard Jan 21 '12 at 12:30
    
Mr.Wizard, i agree. Both your InterpolatingFunction method and Pick-based method in my other answer (after removing Sort from the definition) are uncomparably faster than ReplaceList. However, ReplaceList and pattern-based approaches often have this hard-to-resist simplicity. –  kguler Jan 21 '12 at 13:02
    
I yield; +1 for simplicity. –  Mr.Wizard Jan 21 '12 at 13:15
intervals[x_, list_List] :=
  Cases[
    Partition[Flatten[{-Infinity, Union[list], Infinity}], 2, 1]
  , {l_, u_} /; l <= x <= u
  ]

Use cases:

In[53]:= intervals[3, Range[10]]
Out[53]= {{2,3},{3,4}}

In[54]:= intervals[3, 2 * Range[10]]
Out[54]= {{2,4}}

intervals[-3, Range[10]]
Out[55]= {{-∞,2}}

In[56]:= intervals[999, Range[10]]
Out[56]= {{10,∞}}

In[58]:= intervals[37, {13,8,1,28,87,14,61,20,91,92,37,93,76,83,32}]
Out[58]= {{32,37},{37,61}}
share|improve this answer
    
While working on this question I was surprised to find that out Sort[{4, 3, 2, 1, -∞, ∞}] yielded {1, 2, 3, 4, -∞, ∞} (and Union too). –  WReach Jan 21 '12 at 22:54
2  
That's because Sort[] uses OrderedQ[] by default. Try Sort[{4, 3, 2, 1, -∞, ∞}, Less]. –  J. M. Jan 21 '12 at 23:49
    
+1 for clarity of purpose. –  Brett Champion Jan 22 '12 at 3:58

As it turns out, Combinatorica has the function BinarySearch[] implemented. The code in the package is attributed to Paul Abbott. What follows is a modification of the routine that gives results in the format desired by the OP:

bisect[k_?NumericQ, l_List] := 
 Block[{n = Length[l], lo, mid, hi, el},
   {lo, hi} = {1, n};
   While[lo <= hi,
    If[(el = l[[mid = Quotient[lo + hi, 2]]]) === k,
     Which[
      mid == 1,
      Return[{{-Infinity, First[l]}, Take[l, 2]}],
      mid == n,
      Return[{Take[l, -2], {Last[l], Infinity}}],
      True,
      Return[Partition[Take[l, mid + {-1, 1}], 2, 1]]]];
    If[el > k, hi = mid - 1, lo = mid + 1]
    ];
   Which[
    lo == 1,
    Return[{-Infinity, First[l]}],
    lo == n + 1,
    Return[{Last[l], Infinity}],
    True,
    Return[l[[{lo - 1, lo}]]]
    ]
   ] /; VectorQ[l, NumericQ]

I'll leave to you how to handle the case of the singleton list.

share|improve this answer

Here is another version:

ClearAll[getInterval];
getInterval[ints_List, num_] :=
 Position[UnitStep[ints - num], 1, 1, 1] /.
  {
    {{1}} -> { -Infinity, First@ints},
    {} -> {Last@ints, Infinity},
    {{n_}} :> ints[[n - 1 ;; n]]
  };
share|improve this answer

Among many alternatives you can use something like

glblub1[x_, data_List] := Pick[#, IntervalMemberQ[Interval@#, x] & /@ #]& @
                              ( Partition[#, 2, 1]& @
                                Append[Prepend[Sort@data, -Infinity], Infinity])

or

glblub2[x_, data_List] := Pick[#, (#1 <= x <= #2) & @@@ #]& @ 
                              ( Partition[#, 2, 1]& @
                                Append[Prepend[Sort@data, -Infinity], Infinity]) 

If x is a member of the list and you wish to return x rather than two intervals containing x use as

Intersection@@glblub1[x,data]
Intersection@@glblub2[x,data]

or just redefine the two functions by prefixing both with Intersection@@.

share|improve this answer

WReach's answer prompted me to write another answer:

intervals[x_?NumericQ, list_List] := 
 With[{sl = Sort[Flatten[{-Infinity, list, Infinity}], LessEqual]},
   sl[[{#, # + 1}]] & /@ 
    Flatten[Position[
      Times @@@ Partition[Sign[x - sl], 2, 1], -1 | 0]]] /; 
  VectorQ[list, NumericQ]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.