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

Question

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 $

Answer 1

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}

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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]