First key in OrderedDict that exceeds threshold

Question

Say I have an OrderedDict:

a = OrderedDict([(5, 'a'), (7, 'b'), (10, 'c')])

Is there an efficient way to get the first value whose key exceeds a certain threshold, without looping over all keys?

Examples:

>>> get_first(a, 6)
'a'
>>> get_first(a, 3)
None
>>> get_first(a, 8)
'b'

I would like to avoid having to implement binary search myself. Is there an efficient out-of-the-box implementation available?

First hit for *"Python binary search"*: [`bisect`](https://docs.python.org/2/library/bisect.html). Come on. — jonrsharpe, May 26 '15 at 15:55
If the keys are not in sorted order, so far as I can see there cannot exist an algorithm that is materially faster than looping over the keys. — Kevin, May 26 '15 at 15:59

score 1 · Answer 1 · answered May 26 '15 at 16:01

You don't have to implement a binary search yourself, you can use the bisect for that. However, OrderedDict is not sorted so you can't use a binary search on the dictionary keys unless you sort them first, and that won't be very efficient (in fact it's likely to be faster to just loop over the keys).

If you maintain a sorted list of keys, then that could work, or if you use an implementation of a dictionary that is sorted. You can use the built-in collections.OrderedDict but then you would have to maintain the sorting yourself, or you can use some btree implementation, I think there are several.

I have only used BTree, it's written in C and very fast, but the API is somewhat obtuse.

First key in OrderedDict that exceeds threshold

1 Answers1

Linked