問(wèn)題:
有兩個(gè)已排好序的數(shù)組A和B，長(zhǎng)度均為n，找出這兩個(gè)數(shù)組的中間元素。要求時(shí)間代價(jià)為O(logn)
思路:
a. 比較自然的思路是歸并算法，不過(guò)時(shí)間復(fù)雜度是O(n)，無(wú)法滿足題目要求
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)