please make sure algorithm is in O(lgn) time and a full proof explaining why it works (loop invariant, etc).

4. (20 pts) Let A and B be arrays of integers. Each array contains n elements, and each array is in sorted order (ascending). A and B do not share any elements in common. Give a O(lg n)-time algorithm which finds the median of A U B and prove that it is correct. This algorithm will thus find the median of the 2n elements that would result from putting A and B together into one array. (Note: define the median to be the average of the two middle values of a list with an even number of elements.)