快速求两有序数组合并后的中位数

gxqcn

先解释一下“中位数”的概念：
　　把n个数据按大小顺序排列，处于最中间位置的一个数据（或）叫做这组数据的中位数（median）。
中位数仅与数据排列位置有关，当一组数据从小到大排列后，最中间的数据为中位数（偶数个数据取最中间两个的平均数)。

现在的问题是：给出两个已排序的数组A和B，要求快速得到它们合并后的中位数？
（更一般的，如何快速得到两有序数组合并排序后的任意某个位置上的数据？）

大家有空时讨论讨论。
这是我自编的，也许在某个时候某个领域会有用。

无心人

好像很简单的样子

mathe

csdn里面好像讨论过的

g99

from CSDN:

Say the two arrays are sorted and increasing, namely A and B.
It is easy to find the median of each array in O(1) time.
Assume the median of array A is m and the median of array B is n.
Then,
1' If m=n, then clearly the median after merging is also m, the algorithm holds.
2' If m <n, then reserve the half of sequence A in which all numbers are greater than
  m, also reserve the half of sequence B in which all numbers are smaller than n.
  Run the algorithm on the two new arrays.
3' If m>n, then reserve the half of sequence A in which all numbers are smaller than
  m, also reserve the half of sequence B in which all numbers are larger than n.
  Run the algorithm on the two new arrays.

Time complexity: O(logn)

无心人

归并排序就是这个问题的变形吧

kon3155

csdn有个差不多的
http://topic.csdn.net/u/20090220 ... a-8f9fcfec7a2b.html

litaoye

以前用2分写过1个

http://topic.csdn.net/u/20090117 ... 8-359d3927c145.html