Google : 找中数

两个大小相同的排好序的数组，A和B，如何找出两个数组的中数

基本和两个排好序的数组合成一个大数组的步骤类似吧，甚至还要简单一点（amax<bmin的时候直接拿来计算就好了，反之亦然）。只不过在第n步的时候（假设一个数组长度为n）停止就好了，另外需要记录第n大的和第n+1大的数。
如果两个数组都是从小到大排的那就是：

float result;
if(a[n] < b[0]) result =(a[n]+b[0])/2;
else if(a[0]>b[n]) result=(a[0]+b[n])/2;
else
{
int ia=0,ib=0;
for(int t=0; t < n; t++)
{
        if(a[ia] < b[ib])  ia++;
        else                   ib++;
}
result =(a[ia]+b[ib])/2;
}

O(n)。 每次对半分，看哪半多哪半少，然后变更问题(如找第x大数)继续递归。

找中数，不是平均数。

提示，谁给个O(logn)的解法，合并数组太简单了

回复 4# wwwyhx
我只能想到(logn)^2的。用二分在A中枚举，对每个值在B里二分找它的位置（找lower_bound)，然后根据该元素在整个A和B中所处的位置调整二分的区间

有个性质是A,B合并后的中数是分布在A的中数和B的中数之间，也就是说可以不停的取中数调整大小，每次A排除一半，B排除一半就可以做到logn，这个解法我也没做出来，参考别人的

回复 6# wwwyhx
仔细想想还真是，很巧妙的方法～