Find the Kth Smallest Element of Two Sorted Arrays

Problem: given two sorted arrays, find the Kth smallest element.

Solution: if we have two pointer scanning from the heads of two arrays, we can have an O(K) algorithm. Here we give the main idea of an O(logm + logn) algorithm, where m and n are the length of the two arrays, respectively.

1. We pick the ith and jth elements from two arrays. We make i+j = K-1. Then if Ai > Bj && Ai < Bj+1, Ai is the Kth smallest element. The other way is the same (Ai < Bj).
2. If the previous condition doesn't hold, which means Ai < Bj && Ai < Bj+1. Then the Kth smallest element cannot be within A0 to Ai and Bj+1 to Bn-1. Then we remove them and only need to look for the K-i-1th smallest element in the sub-arrays left.