title: Finding the kth-smallest element in union of sorted arrays
body: <p>I was studying the article on finding the kth-smallest element in the union of two sorted arrays at <a href="http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html" rel="nofollow">leetcode</a>. I don't think that the algorithm is correct. There is this line: <strong>We make an observation that when Ai &lt; Bj, then it must be true that Ai &lt; Bj-1. On the other hand, if Bj &lt; Ai, then Bj &lt; Ai-1.</strong>. How can it be true for any <code>i</code> and <code>j</code>? </p>
  
  <p>And secondly, this line also baffles me: <strong>We try to approach this tricky problem by comparing middle elements of A and B, which we identify as Ai and Bj. If Ai is between Bj and Bj-1, we have just found the i+j+1 smallest element</strong>, although it comes out to be true. Can anyone explain the reason? I really want to understand the algo, I have done it by merging the arrays, but that takes <code>O(N)</code> time, compared to <code>O(log N)</code> time here.</p>