问题:
有两个已排好序的数组A和B，长度均为n，找出这两个数组的中间元素。要求时间代价为O(logn)
思路:
a. 比较自然的思路是归并算法，不过时间复杂度是O(n)，无法满足题目要求
b.
( http://www.binghe.org/2011/05/find-median/ )
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)