題目
給定兩個有序列表疲恢，大小分別為m和n凶朗。給出一個算法，以O(shè)（logn+logm）時間找出兩個列表合并后的有序列表中第k小元素
算法思想
設(shè)兩個數(shù)組為A[1...m],B[1...n]冈闭，則中間位置分別為m/2與n/2俱尼，假設(shè)A[m/2]>B[n/2]，那么A[m/2...m]在A+B的n/2+m/2之后萎攒，此時遇八，若k<n/2+m/2，那么就可以排除A[m/2...m]的元素耍休，在剩余元素再進行上述操作刃永，若k>n/2+m/2，那么就可以排除B[1...n/2]的元素羊精，再剩余元素中尋找第k-n/2小項斯够。
代碼：
#include <iostream>
#define MAXLEN 100
using namespace std;
int Search(int A[],int B[],int aLeft, int aRight, int bLeft, int bRight, int k)
{
int aMiddle = (aLeft + aRight) / 2;
int bMiddle = (bLeft + bRight) / 2;
if (aLeft > aRight)
return B[bLeft + k - 1];
if (bLeft > bRight)
return A[aLeft + k - 1];
if (A[aMiddle] > B[bMiddle])
{
if (k <= (aMiddle - aLeft) + (bMiddle - bLeft) + 2)
return Search(A, B, aLeft, aMiddle - 1, bLeft, bRight, k);
else
return Search(A, B,aLeft, aRight, bMiddle + 1, bRight, k - (bMiddle - bLeft) - 1);
}
else
{
if (k <= (aMiddle - aLeft) + (bMiddle - bLeft) + 2)
return Search(A, B, aLeft, aRight, bLeft, bMiddle - 1, k);
else
return Search(A, B, aMiddle + 1, aRight, bLeft, bRight, k - (aMiddle - aLeft) - 1);
}
}
int main(void)
{
int alen, blen,k;
int A[MAXLEN],B[MAXLEN];
cin >> alen;
for (int i = 0; i < alen; i++)
{
cin >> A[i];
}
cin >> blen;
for (int i = 0; i < blen; i++)
{
cin >> B[i];
}
cin >> k;
cout << "第" << k << "小元素是" << Search(A, B, 0, alen - 1, 0, blen - 1, k) << endl;
system("pause");
return 0;
}
