Median of two array
两个数组的中位数，这道是11CS的DS最后一题，考研的童鞋一定不会陌生，都已经做烂了，但是想想看第一次做的时候，是否能写出正确的处理所有case的代码了。
我也不记得当时有没有写出来了。。。。
这道题目很多帖子，也是经典题目
http://wenku.baidu.com/view/114e577a27284b73f242506b
http://liubangchuan.iteye.com/blog/1870650
http://my.oschina.net/mustang/blog/58047
http://blog.csdn.net/hackbuteer1/article/details/7584838
先来个简单的，假设两个数组等长，且sorted，假设median定义为 两个数组中 中间两个数较小的一个
思路大家基本都知道，就是两个数组同时二分，然后比较, a[mid1]
思想是基于这个：中位数必>=至少”一半”的数，n奇，(n-1)/2 此处写的除都是数学的除，不是C++的除，避免混淆,如果偶数，必>=(n-2)/2),对于等长数组，n比为偶数
(中位数：如果长度为奇，就是排序后中间的数，如果偶，就是中间的两个数的任意一个(leetcode定义为均值))，那么接下来代码AC(如果面试官算法非常强的话，应该是知道你的代码是否可以AC的)之前需要回答几个问题：
- 返回的出口在哪几个地方？
- 奇偶性处理
对于第一个问题，首先如果相等的话，就找到了，因为<=a[mid] 的数至少(n-2)/2， >=a[mid]也一样，b[mid]也一样，所以直接返回中位数了，如果a[mid1]<b[mid1]，a[0…mid1-1] b[0..mid1-1]最多这么多数小于。。。。
突然发现好像看的答案好像只能返回偶数时两个中位数中靠前的一个。。。。。呜呜呜。。。。。。
大致思想是如果<=a[mid]的数都不到一半了，往上移的时候可以多移一位，否则要保留mid，b[]也是一样的。
现附上这个两个等长数组，返回中位数(如果偶数个数时返回中间两个任意都可以的话)代码(由于没有OJ测所以未必保证正确性)：
int findMedianSortedArrays_EqualSize(int A[], int B[], int n)
{
int low1=0,high1=n-1,low2=0,high2=n-1;
while(low1<high1 || low2<high2)
{
int mid1=(low1+high1)/2;
int mid2=(low2+high2)/2;
if(A[mid1]<B[mid2])
{
if(n%2==0)//a[mid1] can not be median of a[]+b[], analyze...
low1=mid1+1,high2=mid2;
else
low1=mid1,high2=mid2;
}
else if(A[mid1]>B[mid2])//对称分析
{
if(n%2==0)
low2=mid2,high2=mid2-1;
else
low2=mid2,high2=mid2;
}
else
{
return A[mid1];
}
}
return A[low1]<B[low2]?A[low1]:B[low2];
}
这个等长的情况已经比较麻烦了，包括最后返回的这两个low1 low2的解释我还没有看到，而不等长的里面还嵌套了一个外部函数的递归，我本打算基于上述这个弄个不等长的，始终搞不出来o(╯□╰)o
不等长的就暂时放一放吧，这个从昨天一直搞到几天，断断续续弄，太浪费时间了，先暂时搁置吧，我用merge方向也过了leetcode，leetcode其实时间很松的。