题目
给定两个有序列表，大小分别为m和n。给出一个算法，以O（logn+logm）时间找出两个列表合并后的有序列表中第k小元素
算法思想
设两个数组为A[1...m],B[1...n]，则中间位置分别为m/2与n/2，假设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;
}
