**Problem:**given two sorted arrays, find the

*K*th 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(log

*m*+

*log*

*n*) algorithm, where

*m*and

*n*are the length of the two arrays, respectively.

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

## No comments:

## Post a Comment