找出两个含有相同元素个数的递增数列中第n小的数

1.Description

You are given two arrays  L1  and  L2 , each with  n  keys sorted in increasing order. For simplicity,you may assume that the keys are all distinct from each other.

(a) Describe an  O(logn)  time algorithm to find the  nth  smallest of the  2n  keys.

(b) Describe an  O(logn)  time algorithm to find the  n2 th smallest (i.e., the median) of the  2n  keys assuming that  n  is even.

public class BinarySearch
{
	public static int Find(int seq1[],int seq2[],int left1,int right1,int left2,int right2,int key)
	{
		int mid1=(left1+right1)/2;
		int mid2=(left2+right2)/2;
		
		if(left1>right1)
		{
			int index=left2+key-1;
			return seq2[index];
		}
		if(left2>right2)
		{
			int index=left1+key-1;
			return seq1[index];
		}
		if(key<=(mid1-left1+mid2-left2+1))
		{
			if(seq1[mid1]<=seq2[mid2])
			{
				right2=mid2-1;
				return Find(seq1,seq2,left1,right1,left2,right2,key);
			}
			else
			{
				right1=mid1-1;
				return Find(seq1,seq2,left1,right1,left2,right2,key);
			}
		}
		else 
		{
			//remove the elements which is smaller than the median value
			if(seq1[mid1]<=seq2[mid2])
			{
				int keyChange=mid1+1-left1;
				left1=mid1+1;
				key=key-keyChange;
				return Find(seq1,seq2,left1,right1,left2,right2,key);
			}
			else
			{
				int keyChange=mid2+1-left2;
				left2=mid2+1;
				key=key-keyChange;
				return Find(seq1,seq2,left1,right1,left2,right2,key);
			}
		}
	}
	public static void main(String[] args)
	{
		int seq1[]={2,3,5,8,10};
		int seq2[]={4,6,7,9,12};
		int left1=0,left2=0,right1=seq1.length-1,right2=seq2.length-1;
		int x1=seq1.length;
		int x2=seq1.length/2;
		int x1Result=Find(seq1,seq2,left1,right1,left2,right2,x1);
		System.out.println("the "+x1+"th smallest number is "+x1Result);
		int x2Result=Find(seq1,seq2,left1,right1,left2,right2,x2);
		System.out.println("the "+x2+"th smallest number is "+x2Result);
	}
	
}