# How to find range in which a number falls, from given list of numbers?

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$

-
And what do you want to happen with f if x is an element of list? –  Ｊ. Ｍ. 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

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}}},
{{Last@list + 1, {Last@list, \[Infinity]}}}
],
InterpolationOrder -> 0
];

intf2[12225.4]
{12211, 12227}
-
Yet another non-obvious gem +1 –  kguler Jan 21 '12 at 13:05
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.

-
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

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}]]]]
-

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}]
-
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}}
-
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
That's because Sort[] uses OrderedQ[] by default. Try Sort[{4, 3, 2, 1, -∞, ∞}, Less]. –  Ｊ. Ｍ. 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.

-

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]]
};
-

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@@.

-