# Can association be used to find the maximum key less than a specific number?

Suppose we have an association assoc.

assoc = <| 1 -> 1, 3 -> 2, 5 -> 3, 7 -> 4, 20 -> 5|>;


Instead of checking if a specific key exists in this association, can I use Association to "efficiently" find the maximum key (or minimum key) which is less(larger) than or equal to a specific value? I.e., I want to find the upper or lower bound of the given Association with in a time less than O(N) where N is the length of the Association. Please note that many kinds of balanced tree data structures allow such functionality.

In this specific example, lower(assoc, 10) == 7 and lower(assoc, 6) == 5 are the desired results. If it cannot be applicable for this situation, what is the best way(or data structure and so on) for this purpose in MMA?

• I'm not sure this is possible in less than O(N) since Association is implemented via a hash table, not a tree structure. – Stefan R Apr 17 '15 at 16:25
• @StefanR It is also ok to confirm that it is not possible :) – Sungmin Apr 17 '15 at 23:27

I believe this is of higher order than you are looking for but it works with an Association.

Max@Select[Keys[assoc], # <= 10 &]
(* 7 *)


Keys gets the keys, Select grabs those less than equal to 10, then Max does its job. As function lower

lower[a_?AssociationQ, boundary_?NumericQ] :=
Max@Select[Keys[a], # <= boundary &]

lower[assoc, 6]
(* 5 *)


Hope this helps.

• Thanks for your help and upvoted it:) However, since it is not strictly looking for (because of the O(N) time complexity), I would like to wait for more answers in case there exist better solutions. – Sungmin Apr 17 '15 at 10:49
• Keys[assoc] returns a list, which can be interpreted as a tree, so I would think that the time complexity on lower[assoc, i] would be linear. Try Table[ With[{assoc = Association[Table[RandomInteger[n] -> RandomInteger[n], {n}]]}, {n, Length@Keys[assoc], Timing[lower[assoc, 6]]}], {n, Flatten[Table[10^i, {i, 7}, {3}]]}] followed by ListLogLogPlot[Transpose[{%[[All, 2]], %[[All, 3, 1]]}], PlotRange -> All] to see that it appears to be... – Josh Bishop Jan 21 '19 at 20:08