Python dictionary - binary search for a key?
<p>I want to write a container class that acts like a dictionary (actually derives from a dict), The keys for this structure will be dates.</p>

<p>When a key (i.e. date) is used to retrieve a value from the class, if the date does not exist then the next available date that preceeds the key is used to return the value.</p>

<p>The following data should help explain the concept further:</p>

<pre><code>Date (key)      Value
2001/01/01      123
2001/01/02       42
2001/01/03      100
2001/01/04      314
2001/01/07      312
2001/01/09      321
</code></pre>

<p>If I try to fetch the value associated with key (date) '2001/01/05' I should get the value stored under the key 2001/01/04 since that key occurs before where the key '2001/01/05' would be if it existed in the dictionary.</p>

<p>In order to do this, I need to be able to do a search (ideally binary, rather than naively looping through every key in the dictionary). I have searched for bsearch dictionary key lookups in Python dictionaries - but have not found anything useful.</p>

<p>Anyway, I want to write a class like that encapsulates this behavior.</p>

<p>This is what I have so far (not much):</p>

<pre><code>#
class NearestNeighborDict(dict):
#
"""
#
a dictionary which returns value of nearest neighbor 
if specified key not found
#
"""

def __init__(self, items={}):
    dict.__init__(self, items)


def get_item(self, key):
    # returns the item stored with the key (if key exists)
    # else it returns the item stored with the key
</code></pre>
