title: Finding kth smallest element in union of 2 sorted array
body: <p>I think this question was asked so many times, but still there aren't any clear solution!
  Anyways, this is what I found as good answer in O(k) (possibly O(logm + logn) too). But I don't understand part, where if M_B > M_A (or other way round) we should be throwing away after elements after M_B. But here its reverse - throwing elements which are before M_B. Can anyone please explain why?</p>
  
  <p><a href="http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s01/recitations/rec03/rec03.ps" rel="nofollow">http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s01/recitations/rec03/rec03.ps</a></p>
  
  <p>And other question is doing K/2 ... we should be doing it, but it isn't obvious to me. </p>
  
  <p>[EDIT 1]</p>
  
  <pre><code>Example
  A = [2, 9, 15, 22, 24, 25, 26, 30]
  B = [1, 4, 5, 7, 18, 22, 27, 33]
  k= 6
  
  Answer is 9 (A[1])
  </code></pre>
  
  <p>Here is what I think, if I want to solve in O(Log k) ... need to throw k/2 elements each time. 
  Base solution: if K &lt; 2: return 2nd smallest element from - A[0], A[1], B[0], B[1]
  else:
  compare A[k/2] and B[k/2]: if A[k/2] &lt; B[k/2]: then kth smallest element will be in A[1 ... n] and B[1 ... K/2] ... okay here I thrower k/2 (can do similar for A[k/2] > B[k/2]. so now question is next time also k index is K or k/2? </p>
  
  <p>What I'm doing is right?</p>