PAT (Advanced Level) 1029. Median (25) 求兩個有序數組的中位數，二分

Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences is defined to be the median of the nondecreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.

Given two increasing sequences of integers, you are asked to find their median.

Input

Each input file contains one test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (<=1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int.

Output

For each test case you should output the median of the two given sequences in a line.

Sample Input

4 11 12 13 14
5 9 10 15 16 17
      

Sample Output

13      

直接歸并的話，在k較大時，效率很低。      

可以用二分法來做。      

舉個例子，有兩個數組a和b升序排列，我們可以把它們看成兩個幫派，幫派裡的兄弟按照實力從弱到強進行升序排列，通常雜事都推給實力弱的人做。      

由于有新的幫派c崛起了，對這兩個幫派造成了威脅。這兩個幫派a和b決定進行合并，這些家夥都有點小心機，都希望合并後，從隔壁幫派過來的，比自己強的少點，比自己弱的多點，這樣自己的地位就高點，以後可以少幹點活。      

好了，現在要找兩個幫派合并後第10弱的人，因為合并後最弱的10個人要組成一個打雜小隊。如果用歸并的話，就先讓兩個幫派最弱的打一架，輸的一方再派出第二弱的，依次類推。這樣打一架确定1個人，打過10架後，最弱的10個人确定，打雜小隊成立了。      
   

有個機智的哥們說這樣太麻煩，既然每個幫派原本都給自己的兄弟排過序。我們可以讓原本兩個幫派第5弱的人a[4]和b[4]打一架，若a[4]<b[4]，即b幫派的哥們赢了，說明合并a[4]最多能再升4級（幹掉b[0]b[1]b[2]b[3]，從第5弱升到第9弱，進而a[0]a[1]a[2]a[3]a[4]這5個可以直接加入打雜小隊，打一架直接确定了一半的人，剩下的人可以用同樣的方法确定。萬一打平就更好了，直接确定10個最弱的。      

/*2015.7.23cyq*/
#include <iostream>
using namespace std;

long A[1000001];
long B[1000001];

int findKth(long A[],long B[],int Na,int Nb,int k){
	if(Na>Nb)//保證數組A較小
		return findKth(B,A,Nb,Na,k);
	if(Na==0)
		return B[k-1];
	if(k==1)
		return min(A[0],B[0]);

	int ia=min(k/2,Na);//數組A可能還不夠k/2個元素
	int ib=k-ia;
	if(A[ia-1]<B[ib-1])//舍棄數組A前面一段
		return findKth(A+ia,B,Na-ia,Nb,k-ia);
	else if(A[ia-1]>B[ib-1])//舍棄數組B前面一段
		return findKth(A,B+ib,Na,Nb-ib,k-ib);
	else//相等，兩個随意輸出一個
		return A[ia-1];

}

int main(){
	int NA,NB;
	scanf("%d",&NA);
	for(int i=0;i<NA;i++)
		scanf("%ld",&A[i]);
	scanf("%d",&NB);
	for(int i=0;i<NB;i++)
		scanf("%ld",&B[i]);
	int mid;
	long result;
	if((NA+NB)%2==0)
		mid=(NA+NB)/2;
	else
		mid=(NA+NB)/2+1;
	printf("%ld",findKth(A,B,NA,NB,mid));
	return 0;
}