Finding closest value in a dictionary
<p>I have a dictionary, <code>T</code>, with keys in the form <code>k,i</code> with an associated value that is a real number (float). Let's suppose I choose a particular key <code>a,b</code> from the dictionary <code>T</code> with corresponding value <code>V1</code>âwhat's the most efficient way to find the closest value to <code>V1</code> for a key that has the form <code>a+1,i</code>, where <code>i</code> is an integer that ranges from 0 to n? (<code>k</code>,<code>a</code>, and <code>b</code> are also integers.) To add one condition on the values of items in <code>T</code>, as <code>i</code> increases in the key, the value associated to <code>T[a+1,i]</code> is strictly increasing (i.e. <code>T[a+1,i+1] &gt; T[a+1,i]</code>).</p>

<p>I was planning to simply run a while loop that starts from <code>i = 0</code> and compares the value<code>T[a+1,i]</code> to <code>V1</code>. To be more clear, the loop would simply stop at the point at which <code>np.abs(T[a+1,i] - V1) &lt; np.abs(T[a+1,i+1] - V1)</code>, as I would know the item associated to <code>T[a+1,i]</code> is the closest to <code>T[a,b] = V1</code>. But given the strictly increasing condition I have imposed, is there a more efficient method than running a while loop that iterates over the dictionary elements? <code>i</code> will go from 0 to n where n could be an integer in the millions. Also, this process would be repeated frequently so efficiency is key. </p>

<p>Since the values for a given <code>a</code> are strictly increasing with successive <code>i</code> values, you can do a binary search for the value that is closest to your target.</p>

<p>While it's certainly possible to write your own binary search code on your dictionary, I suspect you'd have an easier time with a different data structure. If you used nested lists (with <code>a</code> as the index to the outer list, and <code>i</code> as the index to an inner list), you could use the <code>bisect</code> module to search the inner list efficiently.</p>

python python-2.7 loops dictionary iteration