title: Most efficient way to find neighbors in list
body: <p>I have a list of length 2016, but only 242 contain data, the rest is set to None. My aim is to interpolate between the values to fill all gaps with a simple form of IDW (inverse distance weighting).
  So the task of my script is: </p>
  
  <ul>
  <li>Iterate over all items of myList</li>
  <li>If the myList contains a value (that is <strong>not</strong> None), just copy it</li>
  <li>If you find a "None" in myList, get position/value of the left and right neighbor by calculating the distance to all items in myList</li>
  <li>Calculate an interpolated value for the gap from both neighbors (the farer they are away, the less weight they shall get)</li>
  </ul>
  
  <p>Assume we have a smaller list of only 14 items (5 valid ones):</p>
  
  <pre><code>myList = [26, None, None, None, 31, None, None, 58, None, 42, None, None, None, 79]
  resultList = [None] * len(myList)
  
  for i in range(len(myList):
      if not myList[i] is None:
          resultList[i] = myList[i]
      else:
          distance = [i - j for j in range(len(myList)) if not myList[j] is None]
          neighbors = min([n for n in dist if n&gt;0]), max([n for n in dist if n&lt;0])
          # rest of the interpolation (not important for my question):
          neighbors_c = [(1/float(n))**2 for n in neighbors]
          c_sum = sum(neighbors_c)
          neighbors_c = [n/c_sum for n in neighbors_c]
          resultList = myList[i-neighbors[0]]*neighbors_c[0] + myList[i-neighbors[1]]*neighbors_c[1]
  </code></pre>
  
  <p>I am doing that for many many data sets. I found out that this method takes about 0.59sec per data set. What bothers me is the fact that my list is all sorted, but I will only need 2 values from it. So 99% of the distances are calculated for nothing. That led me to attempt two: stop the iteration after i-j becomes negative, because then obviously it ran into the closest values:</p>
  
  <p>So instead of the list comprehension:</p>
  
  <pre><code>distance = [i - j for j in range(len(myList)) if not myList[j] is None]
  </code></pre>
  
  <p>I do a proper for-loop which I quit after distances pass zero and thus become larger again:</p>
  
  <pre><code>dist = []
  for j in range(len(myList)):
      if not myList[j] is None:
          dist.append(i-j)
          if i-j &lt; 0: break
  </code></pre>
  
  <p>With this method I was able to get down to 0.38sec per data set. When iterating over all items in myList, this second method is quick at the beginning (item is hit after 2nd, 3rd, 4th, ... loop and quit immediately), but there is no improvement for the last items, since iteration always starts at j=0.</p>
  
  <p>I wonder if you can think of any quicker way to find the two neighbors of a specific number in a data set, without having to check ALL distances and only taking the largest negative and smalles positive one.</p>
  
  <p>Also, I'm quite new to python, so please let me know if you find other un-pythonic expressions in my script. Thank you guys very much!</p>