title: How to optimally compare if element is in a list of ranges?
body: <p>I have two 2D lists with one million+ entries. <code>List1</code> is full of ranges (e.g. <code>[100, 25]</code> meaning the range starts at <code>100</code> and has a span of <code>25</code>, or <code>100</code> to <code>125</code>) and <code>List2</code> is full of plot points. I have to count how many ranges each point fits into.</p>
  <p>Since I'm dealing with such a large amount of data, I began with a binary search function to make searching for a starting point easier, rather than cycling through the whole list one by one. Except I've modified the search to return the closest index from <code>List1</code> that is ABOVE my plot point, because the plot point is not guaranteed to be an element in <code>List1</code>.</p>
  <p>I end up doing a comparison between each plot point in <code>List2</code> and <code>List1</code>, starting at the index I got from the Binary Search, moving downwards in <code>List1</code> until  the plot point is no longer within a range. Although this works, this is very time consuming and inefficient.</p>
  <pre><code>def findRange(List1, List2):
  
      for plot in List2:
          count = 0
          startIndex = binarySearch(List1, plot)
  
          while plot &lt;= List1[startIndex - 1][0] + 250:
              if List1[startIndex][0] &lt; plot[0] &lt; List1[startIndex][0] + List1[startIndex][1]:
                  count += 1
              startIndex -= 1
  
          plot[1] = count
      return List2
  </code></pre>
  <p>I have the <code>... + 250</code> in the <code>while</code> loop because the range distance can be anywhere from <code>0</code> to <code>250</code>, so I use that to determine whether or not further indices might contain the point.</p>
  <p>I've looked at converting <code>List1</code> into a dictionary where the key is the summed distance, and the value is the number of repeats found. I thought that by getting rid of repeating ranges, I could cut back on some of the overhead. I couldn't find a way to get the correct solution this way though.</p>
  <p>Is there any suggestions you can direct me in to better optimize my algorithm? I can only use the standard library.</p>
  <p>EDIT:</p>
  <pre><code>List1 = [
      [1233, 120],
      [1233, 80],
      [1490, 50],
      [1789, 220],
      [1800, 250]
  ]
   
  List2 = [
      [1300, 0], 
      [1450, 0], 
      [1490, 0], 
      [2000, 0]
  ]
  </code></pre>
  <p>I am supposed to update the zeros in <code>List2</code> with the count of how many ranges the plot point falls into. So an output would be something like this:</p>
  <pre><code>List2 = [
      [1300, 2], # this point can be found in List1[0] and List1[1] because 1300 is between 1233-1353 and 1233-1313
      [1450, 0], # this plot can be found in none of ranges
      [1490, 1], # this plot can be found in List1[2] 
      [2000, 2]  # this plot can be found in List1[2] and List1[3]
  ]
  </code></pre>
  <p>As you can see, the count index is updated in <code>List2</code> from 0 to the number of ranges contains the point.</p>