int findKth(vector<int> &A,vector<int>&B, int startA,int startB,int k){ int lenA=A.size()-startA; int lenB=B.size()-startB; int(lenA>lenB) return findKth(B,A,startB,startA,k); if(lenA==0) return B[startB+k-1]; if(k==1) return min(A[startA],B[startB]); int pa=min(k/2,lenA); int pb=k-pa; if(A[startA+pa-1]>B[startB+pb-1]) return findKth(A,B,startA,startB+pb,k-pb); else if(A[startA+pa-1]<B[startB+pb-1]) return findKth(A,B,startA+pa,startB,k-pa); return A[startA+pa-1]; } int findKth(vector<int>&A,vector<int>&B,int k){ if(k<1||k>A.size()+B.size()) throw runtime_error("k is illegal"); return findKth(A,B,0,0,k); }