這個比較不好講清楚，先假設A和B都是升序的。這個問題的關鍵在於給定k，怎樣找到A和B合併後的第k大元素。我們可以這樣做：1.把A平均分為前後兩個部分，前部分有x個元素，後部分有n1-x個元素（由於A是有序的，所以後一部分的所有元素大於前一部分）。A[x]=A的後一部分的第一個元素。2.同理把B也平均分成前後兩個部分，前部分有y個元素，後部分有n2-y個元素。B[y]=B的後一部分的第一個元素。3.由於兩個陣列都是被平均分割的，所以可以近似地認為x=n1/2,y=n2/2。這裡不妨設A[x]<=B[y]（如果A[x]>B[y]處理過程和下面類似）：===============================情況1============================由於在A中，A[x]前面有x個元素，在B中，B[y]前面有y個元素，並且又有A[x]<=B[y]，那麼，合併以後，A[x]前面原來那些元素必然也在B[y]前面，也就是說，B[y]前面至少會有x+y個元素，我們再規定如果A,B中有相同元素，則合併後A中的元素排在B前面，那麼歸併以後A[x]也會排在B[y]前面，於是乎合併之後B[y]至少有x+y+1個元素。如果k<=x+y+1，也就是說，合併後第k大的元素必然落在B[y]前面。所以，原來在B陣列中，第二部分（B[y]以及B[y]之後）那些元素都不可能包含我們要找到內容（第k大元素），所以我們可以把他們排除掉。這樣就排除了B中一半的內容。===============================情況2============================在A中，A[x]及其後面有n1-x個元素，除去A[x]之後有n1-x-1個元素，B[y]及其後面有n2-y個元素。那麼，由於A[x]<=B[y]，所以合併起來之後，B[y]後面那些元素必然也在A[x]後面，則合併後A[x]後面至少有(n1-x-1)+(n2-y)=(n1+n2)-(x+y+1)個元素。如果k>x+y+1，也就說，合併後第k大的元素必然落在A[x]後面。所以，原來在A陣列中，第一部分（A[x]之前）以及A[x]都不可能包含我們要找的元素，所以我們可以把他們排除掉。這樣就排除了A中一半的內容。============================下面是總結===========================綜上所訴，對於k<=x+y+1還是k>x+y+1我們都提出瞭解決的方案，並且每種方案都能把A或者B的規模減小一半。減小了一半之後，我們將其作為一個新的問題繼續使用上面的演算法處理，直到A或者B減小到足夠小：1.A沒有了，這樣只需要找出B中第k大的元素，也就是B[k].2.B沒有了，同上結果就是A[k].達到以上兩個條件的任意一個分別只需要O(logn1)和O(logn2)的時間，所以最壞情況下這個演算法只需要O(logn1+logn2)就能得出結果。============================下面是程式===========================以下是基於這個演算法的程式，具體實現是在element_at這個函式中，透過呼叫element_at(0,n1-1,0,n2-1,k)可返回A,B數組合並後第k大的元素。#include<stdio.h>intn1,n2;intA[1000];intB[1000];intelement_at(intl1,intr1,intl2,intr2,intk){intx=(l1+r1)/2,y=(l2+r2)/2;if(l1>r1)returnB[l2+k-1];if(l2>r2)returnA[l1+k-1];if(A[x]<=B[y]){if(k<=(x-l1)+(y-l2)+1){returnelement_at(l1,r1,l2,y-1,k);}else{returnelement_at(x+1,r1,l2,r2,k-(x-l1)-1);}}else{if(k<=(x-l1)+(y-l2)+1){returnelement_at(l1,x-1,l2,r2,k);}else{returnelement_at(l1,r1,y+1,r2,k-(y-l2)-1);}}return0;}intmain(){inti;printf("請輸入A的大小：");scanf("%d",&n1);printf("請輸入%d個數，以空格隔開：",n1);for(i=0;i<n1;i++)scanf("%d",&A[i]);printf("請輸入B的大小：");scanf("%d",&n2);printf("請輸入%d個數，以空格隔開：",n2);for(i=0;i<n2;i++)scanf("%d",&B[i]);if((n1+n2)&1){printf("中位數是：%d\n",element_at(0,n1-1,0,n2-1,(n1+n2)/2+1));}else{printf("中位數是：%lf\n",(element_at(0,n1-1,0,n2-1,(n1+n2)/2)+element_at(0,n1-1,0,n2-1,(n1+n2)/2+1))/2.0);}return0;}