title: How to find the kth smallest element in the union of two sorted arrays?
body: <p>This is a homework question, binary search has already been introduced:</p>
  <blockquote>
  <p>Given two arrays, respectively <em>N</em> and <em>M</em> elements in ascending order, not necessarily unique:<br />
  What is a time efficient algorithm to find the <em>k</em>th smallest element in the union of both arrays?</p>
  </blockquote>
  <p>They say it takes <code>O(logN + logM)</code> where <code>N</code> and <code>M</code> are the arrays lengths.</p>
  <p>Let's name the arrays <code>a</code> and <code>b</code>. Obviously we can ignore all <code>a[i]</code> and <code>b[i]</code> where i &gt; k.<br />
  First let's compare <code>a[k/2]</code> and <code>b[k/2]</code>. Let <code>b[k/2]</code> &gt; <code>a[k/2]</code>. Therefore we can discard also all <code>b[i]</code>, where i &gt; k/2.</p>
  <p>Now we have all <code>a[i]</code>, where i &lt; k and all <code>b[i]</code>, where i &lt; k/2 to find the answer.</p>
  <p>What is the next step?</p>