title: Python dictionary - binary search for a key?
body: <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>