# Question: Let X 1 n and Y 1 n

Let X [1 .. n] and Y [1 .. n] be two arrays, each containing n numbers already in sorted order. Give an O (lg n)-time algorithm to find the median of all 2n elements in arrays X and Y.

**View Solution:**## Answer to relevant Questions

Professor Olay is consulting for an oil company, which is planning a large pipeline running east to west through an oil field of n wells. From each well, a spur pipeline is to be connected directly to the main pipeline along ...Define a family ℋ of hash functions from a finite set U to a finite set B to be ¬-universal if for all pairs of distinct elements k and l in U, Pr {h(k) = h(l)} ≤ ¬, where the probability is taken over the ...Show that the longest simple path from a node x in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node x to a descendant leaf.Show how to use an order-statistic tree to count the number of inversions (see Problem 2-4) in an array of size n in time O (n lg n).Professor Canty conjectures that there might exist some ei, ai,j, and ti,j values for which FASTEST-WAY produces li[j] values such that l1[j] = 2 and l2[j] = 1 for some station number j. Assuming that all transfer costs ti, ...Post your question