title: Fast find in list of lists
body: <p>Consider the following function:</p>
  
  <pre><code>import Data.List (find)     
  findInLists items = map $ find (`elem` items)
  </code></pre>
  
  <p>Which can be called like so with the following result:</p>
  
  <pre><code>findInLists [2,3] [[1,2], [1,3,2], [4, -2, 8]] -&gt; [Just 2, Just 3, Nothing]
  </code></pre>
  
  <p>The first argument can be assumed to be sorted, but the second argument will not be sorted.</p>
  
  <p>If <code>n</code> is the total number of items in all lists to be searched (in this particular case, 7, as the search stops once an item is found) and <code>k</code> is the number of items to search for, I believe the runtime of this function will be <code>O(n * k)</code>. However, this is bad for large <code>k</code> when <code>n</code> is also large. </p>
  
  <p>I would like the runtime to be more like <code>O(n * log k) + O(k * log k)</code> or better if possible. What's the best way to do this?</p>