title: Comparison of list of lists using Binary search in Python
body: <p>I have 2 list of lists x(1 million elements) and y(0.1 million elements) and want to get z=x-y.
  each list consist of sub lists of 4 elements each, of which the first element of each sublist is sorted. The first element are strictly increasing and no duplicates are present.
  Now I did this using list comprehension and it roughly takes 6.5 hrs to run it. I wanted to know what is the most time efficient way to do this, keeping in mind that my end result should also be a list of lists.</p>
  
  <p>Secondly, since all my first elements are sorted I thought doing a binary search would be a better idea.
  Idea of binary search - 
  for ex consider I have 2 lists of size x=30 and y=10
  I am looping over elements of y and comparing the first element of each sub list to that of the elemnts in x using binary search, when I find a match that sublist is deleted from the x list.
  So the expected output list should contain 20 elements.But the code I have written gives me 23(it does not delete the last three matches) and I dont know whats wrong with it.
  Heres the code:</p>
  
  <pre><code>def intersection(x,y):
      temp=x[:]
      for i in range(len(y)):
          l=0
          h=len(x)-1
          while l&lt;h:
              mid=l+((h-l)/2)
              if y[i][0]==temp[mid][0]:
                  a=y[i]
                  x.remove(a)
                  break
              elif y[i][0]&gt;temp[mid][0]:
                  if l==mid:
                      break
                  l=mid
              elif y[i][0]&lt;temp[mid][0]:
                  h=mid
      return(x)
  
  
  
  
  
  
  X-List input of 30 elements
  [[1.0, 25.0, 0.0, 0.0]
  [2.0, 0.0, 25.0, 0.0]
  [3.0, 0.0, 50.0, 0.0]
  [4.0, 50.0, 50.0, 0.0]
  [5.0, 50.0, 0.0, 0.0]
  [6.0, 0.0, 25.0, 10.0]
  [7.0, 25.0, 0.0, 10.0]
  [8.0, 50.0, 0.0, 10.0]
  [9.0, 50.0, 50.0, 10.0]
  [10.0, 0.0, 50.0, 10.0]
  [11.0, 0.0, 0.0, 0.0]
  [12.0, 0.0, 0.0, 10.0]
  [13.0, 17.6776695, 17.6776695, 0.0]
  [14.0, 0.0, 34.3113632, 0.0]
  [15.0, 25.9780293, 50.0, 0.0]
  [16.0, 50.0, 25.9780293, 0.0]
  [17.0, 34.3113632, 0.0, 0.0]
  [18.0, 17.6776695, 17.6776695, 10.0]
  [19.0, 34.3113632, 0.0, 10.0]
  [20.0, 50.0, 25.9780293, 10.0]
  [21.0, 25.9780293, 50.0, 10.0]
  [22.0, 0.0, 34.3113632, 10.0]
  [23.0, 11.6599302, 0.0, 0.0]
  [24.0, 0.0, 11.6599302, 0.0]
  [25.0, 0.0, 11.6599302, 10.0]
  [26.0, 11.6599302, 0.0, 10.0]
  [27.0, 27.9121876, 27.9121876, 0.0]
  [28.0, 27.9121876, 27.9121876, 10.0]
  [29.0, 9.77920055, 9.77920055, 0.0]
  [30.0, 9.77920055, 9.77920055, 10.0]]
  Y -List of 10 elements
  [1.0, 25.0, 0.0, 0.0]
  [2.0, 0.0, 25.0, 0.0]
  [11.0, 0.0, 0.0, 0.0]
  [13.0, 17.6776695, 17.6776695, 0.0]
  [14.0, 0.0, 34.3113632, 0.0]
  [17.0, 34.3113632, 0.0, 0.0]
  [23.0, 11.6599302, 0.0, 0.0]
  [24.0, 0.0, 11.6599302, 0.0]
  [27.0, 27.9121876, 27.9121876, 0.0]
  [29.0, 9.77920055, 9.77920055, 0.0]
  ------------------------------------------------------------------------------------------------------------------------------------------Z list (X-Y) the result should be 20 elements but its gives length as 23 elements. it does not remove the remaining 3 elements from the list.
  
  
  
  
  [[3.0, 0.0, 50.0, 0.0],
   [4.0, 50.0, 50.0, 0.0],
   [5.0, 50.0, 0.0, 0.0],
   [6.0, 0.0, 25.0, 10.0],
   [7.0, 25.0, 0.0, 10.0],
   [8.0, 50.0, 0.0, 10.0],
   [9.0, 50.0, 50.0, 10.0],
   [10.0, 0.0, 50.0, 10.0],
   [12.0, 0.0, 0.0, 10.0],
   [15.0, 25.9780293, 50.0, 0.0],
   [16.0, 50.0, 25.9780293, 0.0],
   [18.0, 17.6776695, 17.6776695, 10.0],
   [19.0, 34.3113632, 0.0, 10.0],
   [20.0, 50.0, 25.9780293, 10.0],
   [21.0, 25.9780293, 50.0, 10.0],
   [22.0, 0.0, 34.3113632, 10.0],
   [24.0, 0.0, 11.6599302, 0.0],
   [25.0, 0.0, 11.6599302, 10.0],
   [26.0, 11.6599302, 0.0, 10.0],
   [27.0, 27.9121876, 27.9121876, 0.0],
   [28.0, 27.9121876, 27.9121876, 10.0],
   [29.0, 9.77920055, 9.77920055, 0.0],
   [30.0, 9.77920055, 9.77920055, 10.0]]
  </code></pre>