Algorithm 04 : 寻找两个有序数组中的第N个数，要求时间复杂度为O(logm+logn)
Question : Give a divide and conquer algorithm for the following problem : you are
given two sorted lists of size m and n, and are allowed unit time access
to the ith element of each list. Given an O(logm+logn) time algorithm for
computing the kth largest element in the union of the two lists.
(For simplicity, you can assume that the elements of the two lists are
distinct).

问题：寻找两个有序数组中的第N个数，要求时间复杂度为O(logm+logn)。

/**  * @author YuHuang  * @vision 2011-10-04  * This program is only for algorithm training.  *  */import java.lang.RuntimeException;public class SearchKthNumber {        private int[] aArray;        private int[] bArray;        public SearchKthNumber(int[] aArray,int[] bArray){                this.aArray=aArray;                this.bArray=bArray;                if(this.aArray==null||this.bArray==null){                        throw new RuntimeException("Array should not be null!");                }        }        public int doSearch(int aLeft,int aRight,int bLeft,int bRight,int k){                int aMiddle = (aLeft+aRight)/2;                int bMiddle = (bLeft+bRight)/2;                if(aLeft>aRight){                        return bArray[bLeft+k-1];                }                if(bLeft>bRight){                        return aArray[aLeft+k-1];                }                if(aArray[aMiddle]>bArray[bMiddle]){                        if(k<=(aMiddle-aLeft)+(bMiddle-bLeft)+1){                                return doSearch(aLeft,aMiddle-1,bLeft,bRight,k);                        }else{                                return doSearch(aLeft,aRight,bMiddle+1,bRight,k-(bMiddle-bLeft)-1);                        }                }else{                        if(k<=((aMiddle-aLeft)+(bMiddle-bLeft)+1)){                                return doSearch(aLeft,aRight,bLeft,bMiddle-1,k);                        }else{                                return doSearch(aMiddle+1,aRight,bLeft,bRight,k-(aMiddle-aLeft)-1);                        }                }        }        public static void main(String[] args){                int[] aArray=new int[]{1,3,5,6,8,9,11,18,20};                int[] bArray=new int[]{2,4,7,16,22,29,39,40,55,100};                SearchKthNumber sn=new SearchKthNumber(aArray,bArray);                int k=2;                int result=sn.doSearch(0,aArray.length-1,0,bArray.length-1,k);                System.out.println("The "+k+"th"+" Number : "+result);        }}