Question 1: Let A and B be two sorted arrays of n elements each (thus A + B has 2n elements in total). Give an algorithm that finds the median of A B . This is a number that is larger and equal of half the elements, and is strictly smaller than half of the elements.

Remark: For simplicity assume that every value appears at most once in A B.

Example: A = < 2 ,7 , 19 , 22 > B = <6 , 17 24 25> The number 17 is at least as large as <2 , 6 ,7 17> and smaller than < 19 , 22 , 25 , 25 > Hint: There is a very fast algorithm for this task.