冰河的博客

1.有两个已排好序的数组A和B，长度均为n，找出这两个数组的中间元素。要求时间代价为O(logn)。

然后再论证平均时间复杂度（要不就是最坏时间复杂度）为O(logn)。

大牛给的解法：

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)

2.查找一个数列的中位数

我们算法导论上定义的选择问题(selection problem)：

输入：一个包含n个不同数的集合A和一个数i，1≤i≤n。

输出：元素x∈A，它恰大于A中其他的i-1个元素。

解决选择问题是使用以快速排序算法为模型的分治算法。中位数问题其实就是选择问题的特例，即i=n/2。算法思想如下：

1.抽取数组的第一个元素作为主元，用快速排序的思想进行一次调整，将比主元小的放在左边，比主元大的放在右边。

2.如果主元的索引等于数组长度的一半，那么就找到了。

3.如果主元的索引比数组长度的一半小的话，那么在主元到数组的结尾这个期间内找第（数组长度的一半-主元的索引）大的数。

4.否则在数组的开始到中间值的索引这段期间内找第（数组长度的一半大）大的数。

递归的调用上面的几步，就可以解决问题。复杂度是O(n)