Python: How to get the closest key from the given key?

Question

Given a dictionary:

sample = {
    '123': 'Foo', 
    '456': 'Bar', 
    '789': 'Hello', 
    '-111': 'World'
}

What is the most efficient way (approach and/or data structure) to get the closest (or less) key from a dictionary?

Note:
1. Even if key is a string, comparison should be numerical.
2. Keys can be "negative".

Example:

get_nearest_less_element(sample, '456') # returns 'Bar'
get_nearest_less_element(sample, '235') # returns 'Foo'
get_nearest_less_element(sample, '455') # returns 'Foo'
get_nearest_less_element(sample, '999') # returns 'Hello'
get_nearest_less_element(sample, '0') # returns 'World'
get_nearest_less_element(sample, '-110') # returns 'World'
get_nearest_less_element(sample, '-999') # should return an error since it is beyond the lower bound

Additional question:
Given the same data set, would a sorted OrderedDict or a List of Tuples or any other python data structure be a better approach?

Answer 1

def get_nearest_less_element(d, k):
    k = int(k)
    return d[str(max(key for key in map(int, d.keys()) if key <= k))]

Edit to update with @Paul Hankin's code, but using <= I'm not sure it needs a branch at all. Convert all the keys to numbers, find the ones less than or equal to k, get the max one - if k is in there you'll get it, otherwise you'll get the next biggest - convert back to string and lookup in the dictionary.

Tests: https://repl.it/C2dN/0

I don't know if it's the most efficient idea; since the dictionary you get is unordered, you have to iterate over each element because any of them could be the next biggest, and since you need a numeric comparison you have to convert them all to integers. It seems to me that any other structure would take more initialisation cost as you'd have to go over every item to put it into your structure first.

But it depends on your use case - if k is very likely to be in the dictionary, it makes sense to change my code to have if k in d: return d[k] else: ... branch because not doing the generator expression in that case would be quicker. If it's very likely not in the dictionary, it won't help much.

A pseudocode (untested) version which does sort they keys is below - this would be slower to use once, but possibly faster to query a lot:

# cache to store sorted keys between function calls
# nb. you will have to invalidate this cache (reset to []) 
# when you get a new dictionary
sorted_keys = []

def get_nearest_less_element(d, k):
    if k in d:               # quick return if key is in dict
        return d[k]
    else:

        # costly sort of the keys, only do this once
        if not sorted_keys:
            sorted_keys = sorted(int(key) for key in d.keys())

        # quick run through the sorted key list up
        # to latest item less than k
        k = int(k)
        nearest = sorted_keys[0]
        for item in sorted_keys:
            if item < k:
                nearest = item
            else:
                break

         return d[str(item)]

Answer 2

The below module returns the value if the key is present else it finds the maximum key in a list of keys that are less than the input key.

def get_nearest_less_element(sample,key):
  if key in sample:
    return sample[key]
  else:
    return sample[str(max(x for x in sample.keys() if int(x) < int(key)))]

print get_nearest_less_element(sample, '456')
print get_nearest_less_element(sample, '235')
print get_nearest_less_element(sample, '455')
print get_nearest_less_element(sample, '999')

Output:

Bar

Foo

Foo

Hello

Edit: Edited the answer based on Paul's comment.