Given two sorted lists A[1..n] and B[1..n]. We would like to find the median of the...

Transcribed Image Text:

Given two sorted lists A[1..n] and B[1..n]. We would like to find the median of the union of the two lists. For simplicity, assume that the union of A and B does not contain any duplicate items and that n is a power of 2. The median is the element at position n. i.e., the one that is larger than n-1 elements and less than n elements. (a) Propose a naive algorithm that finds the median in O(n) running time. Given two sorted lists A[1..n] and B[1..n]. We would like to find the median of the union of the two lists. For simplicity, assume that the union of A and B does not contain any duplicate items and that n is a power of 2. The median is the element at position n. i.e., the one that is larger than n-1 elements and less than n elements. (a) Propose a naive algorithm that finds the median in O(n) running time.

Answer rating: 100% (QA)

To find the median of the union of two sorted lists A1n and B1n we can follow a n... View the full answer